1  Mimid : Inferring Grammars

Please note that a complete run can take an hour and a half to complete.

We start with a few Jupyter magics that let us specify examples inline, that can be turned off if needed for faster execution. Switch TOP to False if you do not want examples to complete.

In [1]:

The magics we use are %%var and %top. The %%var lets us specify large strings such as file contents directly without too many escapes. The %top helps with examples.

In [2]:

1.1  Verify System Version

In [3]:

Parts of the program, especially the subprocess execution using do() requires the new flags in 3.7. I am not sure if the taints will work on anything above.

In [4]:
In [5]:
In [6]:

We keep a log of all system commands executed for easier debugging at ./build/do.log.

In [7]:
In [8]:

Try to ensure replicability of measurements.

In [9]:

Note that this notebook was tested on Debian GNU/Linux 8.10 and 9.9 and MacOS Mojave 10.14.5. In particular, I do not know if everything will work on Windows.

In [10]:
In [11]:
Out[11]:
'ProductName:\tMac OS X\nProductVersion:\t10.14.5\nBuildVersion:\t18F132\n'
In [12]:
Out[12]:
'jupyter core     : 4.5.0\njupyter-notebook : 5.7.8\nqtconsole        : 4.5.1\nipython          : 7.6.1\nipykernel        : 5.1.1\njupyter client   : 5.3.1\njupyter lab      : not installed\nnbconvert        : 5.5.0\nipywidgets       : 7.5.0\nnbformat         : 4.4.0\ntraitlets        : 4.3.2\n'

1.2  Install Prerequisites

Our code is based on the utilities provided by the Fuzzingbook. Note that the measurements on time and precision in paper were based on Fuzzingbook 0.0.7. During the development, we found a few bugs in Autogram, which we communicated back, which resulted in a new version of Fuzzingbook 0.8.0.

The fixed Autogram implementation of the Fuzzingbook has better precision rates for Autogram, and timing for grammar generation. However, these numbers still fall short of Mimid for most grammars. Further, the grammars generated by Autogram are still enumerative. That is, rather than producing a context free grammar, it simply appends input strings as alternates to the <START> nonterminal. This again results in bad recall numbers as before. Hence, it does not change our main points. During the remainder of this notebook, we use the 0.8.0 version of the Fuzzingbook.

First we define pip_install(), a helper to silently install required dependencies.

In [13]:
In [14]:
Out[14]:
0

Our external dependencies other than fuzzingbook are as follows.

In [15]:
Out[15]:
0

IMPORTANT: Restart the jupyter server after installation of dependencies and extensions.

We recommend the following jupyter notebook extensions:

In [16]:
Out[16]:
0
In [17]:
Out[17]:
0
In [18]:
In [19]:
Out[19]:
0

1.2.1.1  Table of contents

Please install this extension. The navigation in the notebook is rather hard without this installed.

In [20]:
Out[20]:
0

1.2.1.2  Collapsible headings

Again, do install this extension. This will let you fold away those sections that you do not have an immediate interest in.

In [21]:
Out[21]:
0

1.2.1.3  Execute time

This is not strictly necessary, but can provide a better breakdown than timeit that we use for timing.

In [22]:
Out[22]:
0

1.2.1.4  Code folding

Very helpful for hiding away source contents of libraries that are not for grammar recovery.

In [23]:
Out[23]:
0

1.2.2  Cleanup

To make runs faster, we cache quite a lot of things. Remove build if you change code or samples.

In [24]:
Out[24]:
0

1.2.3  Magic for cell contents

As we mentioned before %%var defines a multi line embedded string that is accessible from Python.

In [25]:
In [26]:
Out[26]:
'# [(\nTesting Mimid\n# )]'

1.3  Our subject programs

Note that our taint tracking implementation is incomplete in that only some of the functions in Python are proxied to preserve taints. Hence, we modify source slightly where necessary to use the proxied functions without affecting the evaluation of the grammar inferencing algorithm.

1.3.1  Calculator.py

This is a really simple calculator written in text book recursive descent style. Note that I have used list() in a few places to help out with taint tracking. This is due to the limitations of my taint tracking prototype. It can be fixed if required by simple AST walkers or better taint trackers.

In [27]:

1.3.2  Mathexpr.py

Originally from here. The mathexpr is much more complicated than our calculator and supports advanced functionalities such as predefined functions and variables.

In [28]:

1.3.3  Microjson.py

The microjson is a complete pure python implementation of JSON parser, that was obtained from from here. Note that we use myio which is an instrumented version of the original io to preserve taints.

In [29]:

1.3.4  URLParse.py

This is the URL parser that is part of the Python distribution. The source was obtained from here.

In [30]:

1.3.5  Netrc.py

Netrc is the initialization file that is read by web-agents such as CURL. Python ships the netrc library in its standard distribution. This was taken from here. Note that we use mylex and myio which corresponds to shlex and io from Python distribution, but instrumented to preserve taints.

In [31]:

1.3.6  CGIDecode.py

The CGIDecode is a program to decode a URL encoded string. The source for this program was obtained from here.

In [32]:

1.3.7  Subject Registry

We store all our subject programs under program_src.

In [33]:

1.4  Rewriting the source to track control flow and taints.

We rewrite the source so that asring in value gets converted to taint_wrap__(astring).in_(value). Note that what we are tracking is not really taints, but rather character accesses to the origin string.

We also rewrite the methods so that method bodies are enclosed in a method__ context manager, any ifconditions and while loops (only while for now) are enclosed in an outer stack__ and inner scope__ context manager. This lets us track when the corresponding scopes are entered into and left.

In [34]:

1.4.1  InRewriter

The InRewriter class handles transforming in statements so that taints can be tracked. It has two methods. The wrap() method transforms any a in lst calls to taint_wrap__(a) in lst.

In [35]:

The wrap() method is internally used by visit_Compare() method to transform a in lst to taint_wrap__(a).in_(lst). We need to do this because Python ties the overriding of in operator to the __contains__() method in the class of lst. In our case, however, very often a is the element tainted and hence proxied. Hence we need a method invoked on the a object.

In [36]:

Tying it together.

In [37]:

1.4.1.1  Using It

In [38]:
In [39]:
taint_wrap__(s).in_(['a', 'b', 'c'])

1.4.2  Rewriter

The Rewriter class handles inserting tracing probes into methods and control structures. Essentially, we insert a with scope for the method body, and a with scope outside both while and if scopes. Finally, we insert a with scope inside the while and if scopes. IMPORTANT: We only implement the while context. Similar should be implemented for the for context.

1.4.2.1  The method context wrapper

A few counters to provide unique identifiers for context managers. Essentially, we number each if and while that we see.

In [40]:

The methods[] array is used to keep track of the current method stack during execution. Epsilon and NoEpsilon are simply constants that I use to indicate whether an IF or a Loop is nullable or not. If it is nullable, I mark it with Epsilon.

In [41]:

The wrap_in_method() generates a wrapper for method definitions.

In [42]:

The method visit_FunctionDef() is the method rewriter that actually does the job.

In [43]:

The rewrite_def() method wraps the function definitions in scopes.

In [44]:

We can use it as follows:

In [45]:
def parse_paren(s, i):
    with method__('parse_paren', [s, i]) as _method__:
        assert s[i] == '('
        i, v = parse_expr(s, i + 1)
        if s[i:] == '':
            raise Exception(s, i)
        assert s[i] == ')'

1.4.2.2  The stack wrapper

The method wrap_in_outer() adds a with ..stack..() context outside the control structures. The stack is used to keep track of the current control structure stack for any character comparison made. Notice the can_empty parameter. This indicates that the particular structure is nullable. For if we can make the condition right away. For while we postpone the decision.

In [46]:

1.4.2.3  The scope wrapper

The method wrap_in_inner() adds a with ...scope..() context immediately inside the control structure. For while, this means simply adding one with ...scope..() just before the first line. For if, this means adding one with ...scope...() each to each branch of the if condition.

In [47]:

1.4.2.4  Rewriting If conditions

While rewriting if conditions, we have to take care of the cascading if conditions (elsif), which is represented as nested if conditions in AST. They do not require separate stack context, but only separate scope contexts.

In [48]:

While rewriting if conditions, we have to take care of the cascading if conditions, which is represented as nested if conditions in AST. We need to identify whether the cascading if conditions (elsif) have an empty orelse clause or not. If it has an empty orelse, then the entire set of if conditions may be excised, and still produce a valid value. Hence, it should be marked as optional. The visit_If() checks if the cascading ifs have an orelse or not.

In [49]:

1.4.2.5  Rewriting while loops

Rewriting while loops are simple. We wrap them in stack and scope contexts. We do not implement the orelse feature yet.

In [50]:

1.4.2.6  Combining both

In [51]:

An example with if conditions.

In [52]:
def parse_paren(s, i):
    assert s[i] == '('
    i, v = parse_expr(s, i+1)
    if s[i:] == '':
        raise Exception(s, i)
    assert s[i] == ')'
In [53]:
def parse_paren(s, i):
    with method__('parse_paren', [s, i]) as _method__:
        assert s[i] == '('
        i, v = parse_expr(s, i + 1)
        with stack__('if', 1, _method__, '-') as if_1_stack__:
            if s[i:] == '':
                with scope__(0, if_1_stack__, _method__) as if_1_0_scope__:
                    raise Exception(s, i)
        assert s[i] == ')'

An example with while loops.

In [54]:
    
def parse_num(s,i):
    n = ''
    while s[i:] and is_digit(s[i]):
        n += s[i]
        i = i +1
In [55]:
def parse_num(s, i):
    with method__('parse_num', [s, i]) as _method__:
        n = ''
        with stack__('while', 1, _method__, '?') as while_1_stack__:
            while s[i:] and is_digit(s[i]):
                with scope__(0, while_1_stack__, _method__
                    ) as while_1_0_scope__:
                    n += s[i]
                    i = i + 1

1.4.2.7  Generating the complete instrumented source

For the complete instrumented source, we need to first make sure that all necessary imports are satisfied. Next, we also need to invoke the parser with the necessary tainted input and output the trace.

In [56]:

1.4.2.8  Using It

In [57]:
In [58]:
from mimid_context import scope__, stack__, method__
import json
import sys
import taints
from taints import taint_wrap__
    
import string


def is_digit(i):
    with method__('is_digit', [i]) as _method__:
        return taint_wrap__(i).in_(list(string.digits))


def parse_num(s, i):
    with method__('parse_num', [s, i]) as _method__:
        n = ''
        with stack__('while', 1, _method__, '?') as while_1_stack__:
            while s[i:] and is_digit(s[i]):
                with scope__(0, while_1_stack__, _method__
                    ) as while_1_0_scope__:
                    n += s[i]
                    i = i + 1
        return i, n


def parse_paren(s, i):
    with method__('parse_paren', [s, i]) as _method__:
        assert s[i] == '('
        i, v = parse_expr(s, i + 1)
        with stack__('if', 1, _method__, '-') as if_1_stack__:
            if s[i:] == '':
                with scope__(0, if_1_stack__, _method__) as if_1_0_scope__:
                    raise Exception(s, i)
        assert s[i] == ')'
        return i + 1, v


def parse_expr(s, i=0):
    with method__('parse_expr', [s, i]) as _method__:
        expr = []
        is_op = True
        with stack__('while', 1, _method__, '?') as while_1_stack__:
            while s[i:]:
                with scope__(0, while_1_stack__, _method__
                    ) as while_1_0_scope__:
                    c = s[i]
                    with stack__('if', 1, _method__, '=') as if_1_stack__:
                        if taint_wrap__(c).in_(list(string.digits)):
                            with scope__(0, if_1_stack__, _method__
                                ) as if_1_0_scope__:
                                if not is_op:
                                    raise Exception(s, i)
                                i, num = parse_num(s, i)
                                expr.append(num)
                                is_op = False
                        elif taint_wrap__(c).in_(['+', '-', '*', '/']):
                            with scope__(1, if_1_stack__, _method__
                                ) as if_1_1_scope__:
                                if is_op:
                                    raise Exception(s, i)
                                expr.append(c)
                                is_op = True
                                i = i + 1
                        elif c == '(':
                            with scope__(2, if_1_stack__, _method__
                                ) as if_1_2_scope__:
                                if not is_op:
                                    raise Exception(s, i)
                                i, cexpr = parse_paren(s, i)
                                expr.append(cexpr)
                                is_op = False
                        elif c == ')':
                            with scope__(3, if_1_stack__, _method__
                                ) as if_1_3_scope__:
                                break
                        else:
                            with scope__(4, if_1_stack__, _method__
                                ) as if_1_4_scope__:
                                raise Exception(s, i)
        with stack__('if', 2, _method__, '-') as if_2_stack__:
            if is_op:
                with scope__(0, if_2_stack__, _method__) as if_2_0_scope__:
                    raise Exception(s, i)
        return i, expr


def main(arg):
    with method__('main', [arg]) as _method__:
        return parse_expr(arg)


if __name__ == "__main__":
    js = []
    for arg in sys.argv[1:]:
        with open(arg) as f:
            mystring = f.read().strip().replace('\n', ' ')
        taints.trace_init()
        tainted_input = taints.wrap_input(mystring)
        main(tainted_input)
        assert tainted_input.comparisons
        j = {
        'comparisons_fmt': 'idx, char, method_call_id',
        'comparisons':taints.convert_comparisons(tainted_input.comparisons, mystring),
        'method_map_fmt': 'method_call_id, method_name, children',
        'method_map': taints.convert_method_map(taints.METHOD_MAP),
        'inputstr': mystring,
        'original': 'calculator.py',
        'arg': arg}
        js.append(j)
    print(json.dumps(js))

1.4.3  Generate Transformed Sources

We will now write the transformed sources.

In [59]:
Out[59]:
0
In [60]:
calculator.py
mathexpr.py
urlparse.py
netrc.py
cgidecode.py
microjson.py

1.4.4  Context Mangers

The context managers are probes inserted into the source code so that we know when execution enters and exits specific control flow structures such as conditionals and loops. Note that source code for these probes are not really a requirement. They can be inserted directly on binaries too, or even dynamically inserted using tools such as dtrace. For now, we make our life simple using AST editing.

1.4.4.1  Method context

The method__ context handles the assignment of method name, as well as storing the method stack.

In [338]:

1.4.4.2  Stack context

The stack context stores the current prefix and handles updating the stack that is stored at the method context.

In [348]:

1.4.4.3  Scope context

The scope context correctly identifies when the control structure is entered into, and exited (in case of loops) and the alternative entered int (in case of if conditions).

In [349]:

1.4.5  Taint Tracker

The taint tracker is essentially a reimplementation of the information flow taints from the Fuzzingbook. It incorporates tracing of character accesses. IMPORTANT: Not all methods are implemented.

In [350]:

We write both files to the appropriate locations.

In [351]:

1.5  Generating Traces

Here is how one can generate traces for the calc program.

In [66]:
Out[66]:
0
In [67]:
Out[67]:
0
In [68]:

Generating traces on mathexpr.

In [69]:
In [70]:
In [71]:
In [72]:
In [73]:
In [74]:

1.6  Mining the Traces Generated

1.6.1  Reconstructing the Method Tree with Attached Character Comparisons

Reconstruct the actual method trace from a trace with the following format

key   : [ mid, method_name, children_ids ]
In [75]:

Here is how one would use it. The first element in the returned tuple is the id of the bottom most method call.

In [76]:
In [77]:
In [78]:
In [79]:
In [80]:
In [81]:
In [82]:
In [83]:
Out[83]:
In [84]:
Out[84]:

1.6.1.1  Identifying last comparisons

We need only the last comparisons made on any index. This means that we should care for only the last parse in an ambiguous parse. However, to make concessions for real world, we also check if we are overwriting a child (HEURISTIC). Note that URLParser is the only parser that needs this heuristic.

In [85]:

Here is how one would use it.

In [86]:
In [87]:
Out[87]:
{0: 6,
 1: 9,
 2: 13,
 3: 18,
 4: 20,
 5: 23,
 6: 28,
 7: 30,
 8: 13,
 9: 35,
 10: 40,
 11: 43,
 12: 48,
 13: 50,
 14: 52}
In [88]:
In [89]:
Out[89]:
{0: 38, 1: 42, 2: 46}

1.6.1.2  Attaching characters to the tree

Add the comparison indexes to the method tree that we constructed

In [90]:

Here is how one would use it. Note which method call each input index is associated. For example, the first index is associated with method call id: 6, which corresponds to is_digit.

In [91]:
In [92]:
Out[92]:
{0: {'id': 0,
  'name': None,
  'children': [{'id': 1,
    'name': 'main',
    'indexes': [],
    'children': [{'id': 2,
      'name': 'parse_expr',
      'indexes': [],
      'children': [{'id': 3,
        'name': 'parse_expr:while_1 ? [1]',
        'indexes': [],
        'children': [{'id': 4,
          'name': 'parse_expr:if_1 = 0#[1, -1]',
          'indexes': [],
          'children': [{'id': 5,
            'name': 'parse_num',
            'indexes': [],
            'children': [{'id': 6,
              'name': 'is_digit',
              'indexes': [0],
              'children': []},
             {'id': 7,
              'name': 'parse_num:while_1 ? [1]',
              'indexes': [],
              'children': []},
             {'id': 8,
              'name': 'is_digit',
              'indexes': [],
              'children': []}]}]}]},
       {'id': 9,
        'name': 'parse_expr:while_1 ? [2]',
        'indexes': [1],
        'children': [{'id': 10,
          'name': 'parse_expr:if_1 = 1#[2, -1]',
          'indexes': [],
          'children': []}]},
       {'id': 11,
        'name': 'parse_expr:while_1 ? [3]',
        'indexes': [],
        'children': [{'id': 12,
          'name': 'parse_expr:if_1 = 2#[3, -1]',
          'indexes': [],
          'children': [{'id': 13,
            'name': 'parse_paren',
            'indexes': [2, 8],
            'children': [{'id': 14,
              'name': 'parse_expr',
              'indexes': [],
              'children': [{'id': 15,
                'name': 'parse_expr:while_1 ? [1]',
                'indexes': [],
                'children': [{'id': 16,
                  'name': 'parse_expr:if_1 = 0#[1, -1]',
                  'indexes': [],
                  'children': [{'id': 17,
                    'name': 'parse_num',
                    'indexes': [],
                    'children': [{'id': 18,
                      'name': 'is_digit',
                      'indexes': [3],
                      'children': []},
                     {'id': 19,
                      'name': 'parse_num:while_1 ? [1]',
                      'indexes': [],
                      'children': []},
                     {'id': 20,
                      'name': 'is_digit',
                      'indexes': [4],
                      'children': []},
                     {'id': 21,
                      'name': 'parse_num:while_1 ? [2]',
                      'indexes': [],
                      'children': []},
                     {'id': 22,
                      'name': 'is_digit',
                      'indexes': [],
                      'children': []}]}]}]},
               {'id': 23,
                'name': 'parse_expr:while_1 ? [2]',
                'indexes': [5],
                'children': [{'id': 24,
                  'name': 'parse_expr:if_1 = 1#[2, -1]',
                  'indexes': [],
                  'children': []}]},
               {'id': 25,
                'name': 'parse_expr:while_1 ? [3]',
                'indexes': [],
                'children': [{'id': 26,
                  'name': 'parse_expr:if_1 = 0#[3, -1]',
                  'indexes': [],
                  'children': [{'id': 27,
                    'name': 'parse_num',
                    'indexes': [],
                    'children': [{'id': 28,
                      'name': 'is_digit',
                      'indexes': [6],
                      'children': []},
                     {'id': 29,
                      'name': 'parse_num:while_1 ? [1]',
                      'indexes': [],
                      'children': []},
                     {'id': 30,
                      'name': 'is_digit',
                      'indexes': [7],
                      'children': []},
                     {'id': 31,
                      'name': 'parse_num:while_1 ? [2]',
                      'indexes': [],
                      'children': []},
                     {'id': 32,
                      'name': 'is_digit',
                      'indexes': [],
                      'children': []}]}]}]},
               {'id': 33,
                'name': 'parse_expr:while_1 ? [4]',
                'indexes': [],
                'children': [{'id': 34,
                  'name': 'parse_expr:if_1 = 3#[4, -1]',
                  'indexes': [],
                  'children': []}]}]}]}]}]},
       {'id': 35,
        'name': 'parse_expr:while_1 ? [4]',
        'indexes': [9],
        'children': [{'id': 36,
          'name': 'parse_expr:if_1 = 1#[4, -1]',
          'indexes': [],
          'children': []}]},
       {'id': 37,
        'name': 'parse_expr:while_1 ? [5]',
        'indexes': [],
        'children': [{'id': 38,
          'name': 'parse_expr:if_1 = 0#[5, -1]',
          'indexes': [],
          'children': [{'id': 39,
            'name': 'parse_num',
            'indexes': [],
            'children': [{'id': 40,
              'name': 'is_digit',
              'indexes': [10],
              'children': []},
             {'id': 41,
              'name': 'parse_num:while_1 ? [1]',
              'indexes': [],
              'children': []},
             {'id': 42,
              'name': 'is_digit',
              'indexes': [],
              'children': []}]}]}]},
       {'id': 43,
        'name': 'parse_expr:while_1 ? [6]',
        'indexes': [11],
        'children': [{'id': 44,
          'name': 'parse_expr:if_1 = 1#[6, -1]',
          'indexes': [],
          'children': []}]},
       {'id': 45,
        'name': 'parse_expr:while_1 ? [7]',
        'indexes': [],
        'children': [{'id': 46,
          'name': 'parse_expr:if_1 = 0#[7, -1]',
          'indexes': [],
          'children': [{'id': 47,
            'name': 'parse_num',
            'indexes': [],
            'children': [{'id': 48,
              'name': 'is_digit',
              'indexes': [12],
              'children': []},
             {'id': 49,
              'name': 'parse_num:while_1 ? [1]',
              'indexes': [],
              'children': []},
             {'id': 50, 'name': 'is_digit', 'indexes': [13], 'children': []},
             {'id': 51,
              'name': 'parse_num:while_1 ? [2]',
              'indexes': [],
              'children': []},
             {'id': 52, 'name': 'is_digit', 'indexes': [14], 'children': []},
             {'id': 53,
              'name': 'parse_num:while_1 ? [3]',
              'indexes': [],
              'children': []}]}]}]}]}]}],
  'indexes': []},
 1: {'id': 1,
  'name': 'main',
  'indexes': [],
  'children': [{'id': 2,
    'name': 'parse_expr',
    'indexes': [],
    'children': [{'id': 3,
      'name': 'parse_expr:while_1 ? [1]',
      'indexes': [],
      'children': [{'id': 4,
        'name': 'parse_expr:if_1 = 0#[1, -1]',
        'indexes': [],
        'children': [{'id': 5,
          'name': 'parse_num',
          'indexes': [],
          'children': [{'id': 6,
            'name': 'is_digit',
            'indexes': [0],
            'children': []},
           {'id': 7,
            'name': 'parse_num:while_1 ? [1]',
            'indexes': [],
            'children': []},
           {'id': 8, 'name': 'is_digit', 'indexes': [], 'children': []}]}]}]},
     {'id': 9,
      'name': 'parse_expr:while_1 ? [2]',
      'indexes': [1],
      'children': [{'id': 10,
        'name': 'parse_expr:if_1 = 1#[2, -1]',
        'indexes': [],
        'children': []}]},
     {'id': 11,
      'name': 'parse_expr:while_1 ? [3]',
      'indexes': [],
      'children': [{'id': 12,
        'name': 'parse_expr:if_1 = 2#[3, -1]',
        'indexes': [],
        'children': [{'id': 13,
          'name': 'parse_paren',
          'indexes': [2, 8],
          'children': [{'id': 14,
            'name': 'parse_expr',
            'indexes': [],
            'children': [{'id': 15,
              'name': 'parse_expr:while_1 ? [1]',
              'indexes': [],
              'children': [{'id': 16,
                'name': 'parse_expr:if_1 = 0#[1, -1]',
                'indexes': [],
                'children': [{'id': 17,
                  'name': 'parse_num',
                  'indexes': [],
                  'children': [{'id': 18,
                    'name': 'is_digit',
                    'indexes': [3],
                    'children': []},
                   {'id': 19,
                    'name': 'parse_num:while_1 ? [1]',
                    'indexes': [],
                    'children': []},
                   {'id': 20,
                    'name': 'is_digit',
                    'indexes': [4],
                    'children': []},
                   {'id': 21,
                    'name': 'parse_num:while_1 ? [2]',
                    'indexes': [],
                    'children': []},
                   {'id': 22,
                    'name': 'is_digit',
                    'indexes': [],
                    'children': []}]}]}]},
             {'id': 23,
              'name': 'parse_expr:while_1 ? [2]',
              'indexes': [5],
              'children': [{'id': 24,
                'name': 'parse_expr:if_1 = 1#[2, -1]',
                'indexes': [],
                'children': []}]},
             {'id': 25,
              'name': 'parse_expr:while_1 ? [3]',
              'indexes': [],
              'children': [{'id': 26,
                'name': 'parse_expr:if_1 = 0#[3, -1]',
                'indexes': [],
                'children': [{'id': 27,
                  'name': 'parse_num',
                  'indexes': [],
                  'children': [{'id': 28,
                    'name': 'is_digit',
                    'indexes': [6],
                    'children': []},
                   {'id': 29,
                    'name': 'parse_num:while_1 ? [1]',
                    'indexes': [],
                    'children': []},
                   {'id': 30,
                    'name': 'is_digit',
                    'indexes': [7],
                    'children': []},
                   {'id': 31,
                    'name': 'parse_num:while_1 ? [2]',
                    'indexes': [],
                    'children': []},
                   {'id': 32,
                    'name': 'is_digit',
                    'indexes': [],
                    'children': []}]}]}]},
             {'id': 33,
              'name': 'parse_expr:while_1 ? [4]',
              'indexes': [],
              'children': [{'id': 34,
                'name': 'parse_expr:if_1 = 3#[4, -1]',
                'indexes': [],
                'children': []}]}]}]}]}]},
     {'id': 35,
      'name': 'parse_expr:while_1 ? [4]',
      'indexes': [9],
      'children': [{'id': 36,
        'name': 'parse_expr:if_1 = 1#[4, -1]',
        'indexes': [],
        'children': []}]},
     {'id': 37,
      'name': 'parse_expr:while_1 ? [5]',
      'indexes': [],
      'children': [{'id': 38,
        'name': 'parse_expr:if_1 = 0#[5, -1]',
        'indexes': [],
        'children': [{'id': 39,
          'name': 'parse_num',
          'indexes': [],
          'children': [{'id': 40,
            'name': 'is_digit',
            'indexes': [10],
            'children': []},
           {'id': 41,
            'name': 'parse_num:while_1 ? [1]',
            'indexes': [],
            'children': []},
           {'id': 42, 'name': 'is_digit', 'indexes': [], 'children': []}]}]}]},
     {'id': 43,
      'name': 'parse_expr:while_1 ? [6]',
      'indexes': [11],
      'children': [{'id': 44,
        'name': 'parse_expr:if_1 = 1#[6, -1]',
        'indexes': [],
        'children': []}]},
     {'id': 45,
      'name': 'parse_expr:while_1 ? [7]',
      'indexes': [],
      'children': [{'id': 46,
        'name': 'parse_expr:if_1 = 0#[7, -1]',
        'indexes': [],
        'children': [{'id': 47,
          'name': 'parse_num',
          'indexes': [],
          'children': [{'id': 48,
            'name': 'is_digit',
            'indexes': [12],
            'children': []},
           {'id': 49,
            'name': 'parse_num:while_1 ? [1]',
            'indexes': [],
            'children': []},
           {'id': 50, 'name': 'is_digit', 'indexes': [13], 'children': []},
           {'id': 51,
            'name': 'parse_num:while_1 ? [2]',
            'indexes': [],
            'children': []},
           {'id': 52, 'name': 'is_digit', 'indexes': [14], 'children': []},
           {'id': 53,
            'name': 'parse_num:while_1 ? [3]',
            'indexes': [],
            'children': []}]}]}]}]}]},
 2: {'id': 2,
  'name': 'parse_expr',
  'indexes': [],
  'children': [{'id': 3,
    'name': 'parse_expr:while_1 ? [1]',
    'indexes': [],
    'children': [{'id': 4,
      'name': 'parse_expr:if_1 = 0#[1, -1]',
      'indexes': [],
      'children': [{'id': 5,
        'name': 'parse_num',
        'indexes': [],
        'children': [{'id': 6,
          'name': 'is_digit',
          'indexes': [0],
          'children': []},
         {'id': 7,
          'name': 'parse_num:while_1 ? [1]',
          'indexes': [],
          'children': []},
         {'id': 8, 'name': 'is_digit', 'indexes': [], 'children': []}]}]}]},
   {'id': 9,
    'name': 'parse_expr:while_1 ? [2]',
    'indexes': [1],
    'children': [{'id': 10,
      'name': 'parse_expr:if_1 = 1#[2, -1]',
      'indexes': [],
      'children': []}]},
   {'id': 11,
    'name': 'parse_expr:while_1 ? [3]',
    'indexes': [],
    'children': [{'id': 12,
      'name': 'parse_expr:if_1 = 2#[3, -1]',
      'indexes': [],
      'children': [{'id': 13,
        'name': 'parse_paren',
        'indexes': [2, 8],
        'children': [{'id': 14,
          'name': 'parse_expr',
          'indexes': [],
          'children': [{'id': 15,
            'name': 'parse_expr:while_1 ? [1]',
            'indexes': [],
            'children': [{'id': 16,
              'name': 'parse_expr:if_1 = 0#[1, -1]',
              'indexes': [],
              'children': [{'id': 17,
                'name': 'parse_num',
                'indexes': [],
                'children': [{'id': 18,
                  'name': 'is_digit',
                  'indexes': [3],
                  'children': []},
                 {'id': 19,
                  'name': 'parse_num:while_1 ? [1]',
                  'indexes': [],
                  'children': []},
                 {'id': 20,
                  'name': 'is_digit',
                  'indexes': [4],
                  'children': []},
                 {'id': 21,
                  'name': 'parse_num:while_1 ? [2]',
                  'indexes': [],
                  'children': []},
                 {'id': 22,
                  'name': 'is_digit',
                  'indexes': [],
                  'children': []}]}]}]},
           {'id': 23,
            'name': 'parse_expr:while_1 ? [2]',
            'indexes': [5],
            'children': [{'id': 24,
              'name': 'parse_expr:if_1 = 1#[2, -1]',
              'indexes': [],
              'children': []}]},
           {'id': 25,
            'name': 'parse_expr:while_1 ? [3]',
            'indexes': [],
            'children': [{'id': 26,
              'name': 'parse_expr:if_1 = 0#[3, -1]',
              'indexes': [],
              'children': [{'id': 27,
                'name': 'parse_num',
                'indexes': [],
                'children': [{'id': 28,
                  'name': 'is_digit',
                  'indexes': [6],
                  'children': []},
                 {'id': 29,
                  'name': 'parse_num:while_1 ? [1]',
                  'indexes': [],
                  'children': []},
                 {'id': 30,
                  'name': 'is_digit',
                  'indexes': [7],
                  'children': []},
                 {'id': 31,
                  'name': 'parse_num:while_1 ? [2]',
                  'indexes': [],
                  'children': []},
                 {'id': 32,
                  'name': 'is_digit',
                  'indexes': [],
                  'children': []}]}]}]},
           {'id': 33,
            'name': 'parse_expr:while_1 ? [4]',
            'indexes': [],
            'children': [{'id': 34,
              'name': 'parse_expr:if_1 = 3#[4, -1]',
              'indexes': [],
              'children': []}]}]}]}]}]},
   {'id': 35,
    'name': 'parse_expr:while_1 ? [4]',
    'indexes': [9],
    'children': [{'id': 36,
      'name': 'parse_expr:if_1 = 1#[4, -1]',
      'indexes': [],
      'children': []}]},
   {'id': 37,
    'name': 'parse_expr:while_1 ? [5]',
    'indexes': [],
    'children': [{'id': 38,
      'name': 'parse_expr:if_1 = 0#[5, -1]',
      'indexes': [],
      'children': [{'id': 39,
        'name': 'parse_num',
        'indexes': [],
        'children': [{'id': 40,
          'name': 'is_digit',
          'indexes': [10],
          'children': []},
         {'id': 41,
          'name': 'parse_num:while_1 ? [1]',
          'indexes': [],
          'children': []},
         {'id': 42, 'name': 'is_digit', 'indexes': [], 'children': []}]}]}]},
   {'id': 43,
    'name': 'parse_expr:while_1 ? [6]',
    'indexes': [11],
    'children': [{'id': 44,
      'name': 'parse_expr:if_1 = 1#[6, -1]',
      'indexes': [],
      'children': []}]},
   {'id': 45,
    'name': 'parse_expr:while_1 ? [7]',
    'indexes': [],
    'children': [{'id': 46,
      'name': 'parse_expr:if_1 = 0#[7, -1]',
      'indexes': [],
      'children': [{'id': 47,
        'name': 'parse_num',
        'indexes': [],
        'children': [{'id': 48,
          'name': 'is_digit',
          'indexes': [12],
          'children': []},
         {'id': 49,
          'name': 'parse_num:while_1 ? [1]',
          'indexes': [],
          'children': []},
         {'id': 50, 'name': 'is_digit', 'indexes': [13], 'children': []},
         {'id': 51,
          'name': 'parse_num:while_1 ? [2]',
          'indexes': [],
          'children': []},
         {'id': 52, 'name': 'is_digit', 'indexes': [14], 'children': []},
         {'id': 53,
          'name': 'parse_num:while_1 ? [3]',
          'indexes': [],
          'children': []}]}]}]}]},
 3: {'id': 3,
  'name': 'parse_expr:while_1 ? [1]',
  'indexes': [],
  'children': [{'id': 4,
    'name': 'parse_expr:if_1 = 0#[1, -1]',
    'indexes': [],
    'children': [{'id': 5,
      'name': 'parse_num',
      'indexes': [],
      'children': [{'id': 6,
        'name': 'is_digit',
        'indexes': [0],
        'children': []},
       {'id': 7,
        'name': 'parse_num:while_1 ? [1]',
        'indexes': [],
        'children': []},
       {'id': 8, 'name': 'is_digit', 'indexes': [], 'children': []}]}]}]},
 9: {'id': 9,
  'name': 'parse_expr:while_1 ? [2]',
  'indexes': [1],
  'children': [{'id': 10,
    'name': 'parse_expr:if_1 = 1#[2, -1]',
    'indexes': [],
    'children': []}]},
 11: {'id': 11,
  'name': 'parse_expr:while_1 ? [3]',
  'indexes': [],
  'children': [{'id': 12,
    'name': 'parse_expr:if_1 = 2#[3, -1]',
    'indexes': [],
    'children': [{'id': 13,
      'name': 'parse_paren',
      'indexes': [2, 8],
      'children': [{'id': 14,
        'name': 'parse_expr',
        'indexes': [],
        'children': [{'id': 15,
          'name': 'parse_expr:while_1 ? [1]',
          'indexes': [],
          'children': [{'id': 16,
            'name': 'parse_expr:if_1 = 0#[1, -1]',
            'indexes': [],
            'children': [{'id': 17,
              'name': 'parse_num',
              'indexes': [],
              'children': [{'id': 18,
                'name': 'is_digit',
                'indexes': [3],
                'children': []},
               {'id': 19,
                'name': 'parse_num:while_1 ? [1]',
                'indexes': [],
                'children': []},
               {'id': 20, 'name': 'is_digit', 'indexes': [4], 'children': []},
               {'id': 21,
                'name': 'parse_num:while_1 ? [2]',
                'indexes': [],
                'children': []},
               {'id': 22,
                'name': 'is_digit',
                'indexes': [],
                'children': []}]}]}]},
         {'id': 23,
          'name': 'parse_expr:while_1 ? [2]',
          'indexes': [5],
          'children': [{'id': 24,
            'name': 'parse_expr:if_1 = 1#[2, -1]',
            'indexes': [],
            'children': []}]},
         {'id': 25,
          'name': 'parse_expr:while_1 ? [3]',
          'indexes': [],
          'children': [{'id': 26,
            'name': 'parse_expr:if_1 = 0#[3, -1]',
            'indexes': [],
            'children': [{'id': 27,
              'name': 'parse_num',
              'indexes': [],
              'children': [{'id': 28,
                'name': 'is_digit',
                'indexes': [6],
                'children': []},
               {'id': 29,
                'name': 'parse_num:while_1 ? [1]',
                'indexes': [],
                'children': []},
               {'id': 30, 'name': 'is_digit', 'indexes': [7], 'children': []},
               {'id': 31,
                'name': 'parse_num:while_1 ? [2]',
                'indexes': [],
                'children': []},
               {'id': 32,
                'name': 'is_digit',
                'indexes': [],
                'children': []}]}]}]},
         {'id': 33,
          'name': 'parse_expr:while_1 ? [4]',
          'indexes': [],
          'children': [{'id': 34,
            'name': 'parse_expr:if_1 = 3#[4, -1]',
            'indexes': [],
            'children': []}]}]}]}]}]},
 35: {'id': 35,
  'name': 'parse_expr:while_1 ? [4]',
  'indexes': [9],
  'children': [{'id': 36,
    'name': 'parse_expr:if_1 = 1#[4, -1]',
    'indexes': [],
    'children': []}]},
 37: {'id': 37,
  'name': 'parse_expr:while_1 ? [5]',
  'indexes': [],
  'children': [{'id': 38,
    'name': 'parse_expr:if_1 = 0#[5, -1]',
    'indexes': [],
    'children': [{'id': 39,
      'name': 'parse_num',
      'indexes': [],
      'children': [{'id': 40,
        'name': 'is_digit',
        'indexes': [10],
        'children': []},
       {'id': 41,
        'name': 'parse_num:while_1 ? [1]',
        'indexes': [],
        'children': []},
       {'id': 42, 'name': 'is_digit', 'indexes': [], 'children': []}]}]}]},
 43: {'id': 43,
  'name': 'parse_expr:while_1 ? [6]',
  'indexes': [11],
  'children': [{'id': 44,
    'name': 'parse_expr:if_1 = 1#[6, -1]',
    'indexes': [],
    'children': []}]},
 45: {'id': 45,
  'name': 'parse_expr:while_1 ? [7]',
  'indexes': [],
  'children': [{'id': 46,
    'name': 'parse_expr:if_1 = 0#[7, -1]',
    'indexes': [],
    'children': [{'id': 47,
      'name': 'parse_num',
      'indexes': [],
      'children': [{'id': 48,
        'name': 'is_digit',
        'indexes': [12],
        'children': []},
       {'id': 49,
        'name': 'parse_num:while_1 ? [1]',
        'indexes': [],
        'children': []},
       {'id': 50, 'name': 'is_digit', 'indexes': [13], 'children': []},
       {'id': 51,
        'name': 'parse_num:while_1 ? [2]',
        'indexes': [],
        'children': []},
       {'id': 52, 'name': 'is_digit', 'indexes': [14], 'children': []},
       {'id': 53,
        'name': 'parse_num:while_1 ? [3]',
        'indexes': [],
        'children': []}]}]}]},
 4: {'id': 4,
  'name': 'parse_expr:if_1 = 0#[1, -1]',
  'indexes': [],
  'children': [{'id': 5,
    'name': 'parse_num',
    'indexes': [],
    'children': [{'id': 6, 'name': 'is_digit', 'indexes': [0], 'children': []},
     {'id': 7,
      'name': 'parse_num:while_1 ? [1]',
      'indexes': [],
      'children': []},
     {'id': 8, 'name': 'is_digit', 'indexes': [], 'children': []}]}]},
 5: {'id': 5,
  'name': 'parse_num',
  'indexes': [],
  'children': [{'id': 6, 'name': 'is_digit', 'indexes': [0], 'children': []},
   {'id': 7, 'name': 'parse_num:while_1 ? [1]', 'indexes': [], 'children': []},
   {'id': 8, 'name': 'is_digit', 'indexes': [], 'children': []}]},
 6: {'id': 6, 'name': 'is_digit', 'indexes': [0], 'children': []},
 7: {'id': 7,
  'name': 'parse_num:while_1 ? [1]',
  'indexes': [],
  'children': []},
 8: {'id': 8, 'name': 'is_digit', 'indexes': [], 'children': []},
 10: {'id': 10,
  'name': 'parse_expr:if_1 = 1#[2, -1]',
  'indexes': [],
  'children': []},
 12: {'id': 12,
  'name': 'parse_expr:if_1 = 2#[3, -1]',
  'indexes': [],
  'children': [{'id': 13,
    'name': 'parse_paren',
    'indexes': [2, 8],
    'children': [{'id': 14,
      'name': 'parse_expr',
      'indexes': [],
      'children': [{'id': 15,
        'name': 'parse_expr:while_1 ? [1]',
        'indexes': [],
        'children': [{'id': 16,
          'name': 'parse_expr:if_1 = 0#[1, -1]',
          'indexes': [],
          'children': [{'id': 17,
            'name': 'parse_num',
            'indexes': [],
            'children': [{'id': 18,
              'name': 'is_digit',
              'indexes': [3],
              'children': []},
             {'id': 19,
              'name': 'parse_num:while_1 ? [1]',
              'indexes': [],
              'children': []},
             {'id': 20, 'name': 'is_digit', 'indexes': [4], 'children': []},
             {'id': 21,
              'name': 'parse_num:while_1 ? [2]',
              'indexes': [],
              'children': []},
             {'id': 22,
              'name': 'is_digit',
              'indexes': [],
              'children': []}]}]}]},
       {'id': 23,
        'name': 'parse_expr:while_1 ? [2]',
        'indexes': [5],
        'children': [{'id': 24,
          'name': 'parse_expr:if_1 = 1#[2, -1]',
          'indexes': [],
          'children': []}]},
       {'id': 25,
        'name': 'parse_expr:while_1 ? [3]',
        'indexes': [],
        'children': [{'id': 26,
          'name': 'parse_expr:if_1 = 0#[3, -1]',
          'indexes': [],
          'children': [{'id': 27,
            'name': 'parse_num',
            'indexes': [],
            'children': [{'id': 28,
              'name': 'is_digit',
              'indexes': [6],
              'children': []},
             {'id': 29,
              'name': 'parse_num:while_1 ? [1]',
              'indexes': [],
              'children': []},
             {'id': 30, 'name': 'is_digit', 'indexes': [7], 'children': []},
             {'id': 31,
              'name': 'parse_num:while_1 ? [2]',
              'indexes': [],
              'children': []},
             {'id': 32,
              'name': 'is_digit',
              'indexes': [],
              'children': []}]}]}]},
       {'id': 33,
        'name': 'parse_expr:while_1 ? [4]',
        'indexes': [],
        'children': [{'id': 34,
          'name': 'parse_expr:if_1 = 3#[4, -1]',
          'indexes': [],
          'children': []}]}]}]}]},
 13: {'id': 13,
  'name': 'parse_paren',
  'indexes': [2, 8],
  'children': [{'id': 14,
    'name': 'parse_expr',
    'indexes': [],
    'children': [{'id': 15,
      'name': 'parse_expr:while_1 ? [1]',
      'indexes': [],
      'children': [{'id': 16,
        'name': 'parse_expr:if_1 = 0#[1, -1]',
        'indexes': [],
        'children': [{'id': 17,
          'name': 'parse_num',
          'indexes': [],
          'children': [{'id': 18,
            'name': 'is_digit',
            'indexes': [3],
            'children': []},
           {'id': 19,
            'name': 'parse_num:while_1 ? [1]',
            'indexes': [],
            'children': []},
           {'id': 20, 'name': 'is_digit', 'indexes': [4], 'children': []},
           {'id': 21,
            'name': 'parse_num:while_1 ? [2]',
            'indexes': [],
            'children': []},
           {'id': 22, 'name': 'is_digit', 'indexes': [], 'children': []}]}]}]},
     {'id': 23,
      'name': 'parse_expr:while_1 ? [2]',
      'indexes': [5],
      'children': [{'id': 24,
        'name': 'parse_expr:if_1 = 1#[2, -1]',
        'indexes': [],
        'children': []}]},
     {'id': 25,
      'name': 'parse_expr:while_1 ? [3]',
      'indexes': [],
      'children': [{'id': 26,
        'name': 'parse_expr:if_1 = 0#[3, -1]',
        'indexes': [],
        'children': [{'id': 27,
          'name': 'parse_num',
          'indexes': [],
          'children': [{'id': 28,
            'name': 'is_digit',
            'indexes': [6],
            'children': []},
           {'id': 29,
            'name': 'parse_num:while_1 ? [1]',
            'indexes': [],
            'children': []},
           {'id': 30, 'name': 'is_digit', 'indexes': [7], 'children': []},
           {'id': 31,
            'name': 'parse_num:while_1 ? [2]',
            'indexes': [],
            'children': []},
           {'id': 32, 'name': 'is_digit', 'indexes': [], 'children': []}]}]}]},
     {'id': 33,
      'name': 'parse_expr:while_1 ? [4]',
      'indexes': [],
      'children': [{'id': 34,
        'name': 'parse_expr:if_1 = 3#[4, -1]',
        'indexes': [],
        'children': []}]}]}]},
 14: {'id': 14,
  'name': 'parse_expr',
  'indexes': [],
  'children': [{'id': 15,
    'name': 'parse_expr:while_1 ? [1]',
    'indexes': [],
    'children': [{'id': 16,
      'name': 'parse_expr:if_1 = 0#[1, -1]',
      'indexes': [],
      'children': [{'id': 17,
        'name': 'parse_num',
        'indexes': [],
        'children': [{'id': 18,
          'name': 'is_digit',
          'indexes': [3],
          'children': []},
         {'id': 19,
          'name': 'parse_num:while_1 ? [1]',
          'indexes': [],
          'children': []},
         {'id': 20, 'name': 'is_digit', 'indexes': [4], 'children': []},
         {'id': 21,
          'name': 'parse_num:while_1 ? [2]',
          'indexes': [],
          'children': []},
         {'id': 22, 'name': 'is_digit', 'indexes': [], 'children': []}]}]}]},
   {'id': 23,
    'name': 'parse_expr:while_1 ? [2]',
    'indexes': [5],
    'children': [{'id': 24,
      'name': 'parse_expr:if_1 = 1#[2, -1]',
      'indexes': [],
      'children': []}]},
   {'id': 25,
    'name': 'parse_expr:while_1 ? [3]',
    'indexes': [],
    'children': [{'id': 26,
      'name': 'parse_expr:if_1 = 0#[3, -1]',
      'indexes': [],
      'children': [{'id': 27,
        'name': 'parse_num',
        'indexes': [],
        'children': [{'id': 28,
          'name': 'is_digit',
          'indexes': [6],
          'children': []},
         {'id': 29,
          'name': 'parse_num:while_1 ? [1]',
          'indexes': [],
          'children': []},
         {'id': 30, 'name': 'is_digit', 'indexes': [7], 'children': []},
         {'id': 31,
          'name': 'parse_num:while_1 ? [2]',
          'indexes': [],
          'children': []},
         {'id': 32, 'name': 'is_digit', 'indexes': [], 'children': []}]}]}]},
   {'id': 33,
    'name': 'parse_expr:while_1 ? [4]',
    'indexes': [],
    'children': [{'id': 34,
      'name': 'parse_expr:if_1 = 3#[4, -1]',
      'indexes': [],
      'children': []}]}]},
 15: {'id': 15,
  'name': 'parse_expr:while_1 ? [1]',
  'indexes': [],
  'children': [{'id': 16,
    'name': 'parse_expr:if_1 = 0#[1, -1]',
    'indexes': [],
    'children': [{'id': 17,
      'name': 'parse_num',
      'indexes': [],
      'children': [{'id': 18,
        'name': 'is_digit',
        'indexes': [3],
        'children': []},
       {'id': 19,
        'name': 'parse_num:while_1 ? [1]',
        'indexes': [],
        'children': []},
       {'id': 20, 'name': 'is_digit', 'indexes': [4], 'children': []},
       {'id': 21,
        'name': 'parse_num:while_1 ? [2]',
        'indexes': [],
        'children': []},
       {'id': 22, 'name': 'is_digit', 'indexes': [], 'children': []}]}]}]},
 23: {'id': 23,
  'name': 'parse_expr:while_1 ? [2]',
  'indexes': [5],
  'children': [{'id': 24,
    'name': 'parse_expr:if_1 = 1#[2, -1]',
    'indexes': [],
    'children': []}]},
 25: {'id': 25,
  'name': 'parse_expr:while_1 ? [3]',
  'indexes': [],
  'children': [{'id': 26,
    'name': 'parse_expr:if_1 = 0#[3, -1]',
    'indexes': [],
    'children': [{'id': 27,
      'name': 'parse_num',
      'indexes': [],
      'children': [{'id': 28,
        'name': 'is_digit',
        'indexes': [6],
        'children': []},
       {'id': 29,
        'name': 'parse_num:while_1 ? [1]',
        'indexes': [],
        'children': []},
       {'id': 30, 'name': 'is_digit', 'indexes': [7], 'children': []},
       {'id': 31,
        'name': 'parse_num:while_1 ? [2]',
        'indexes': [],
        'children': []},
       {'id': 32, 'name': 'is_digit', 'indexes': [], 'children': []}]}]}]},
 33: {'id': 33,
  'name': 'parse_expr:while_1 ? [4]',
  'indexes': [],
  'children': [{'id': 34,
    'name': 'parse_expr:if_1 = 3#[4, -1]',
    'indexes': [],
    'children': []}]},
 16: {'id': 16,
  'name': 'parse_expr:if_1 = 0#[1, -1]',
  'indexes': [],
  'children': [{'id': 17,
    'name': 'parse_num',
    'indexes': [],
    'children': [{'id': 18,
      'name': 'is_digit',
      'indexes': [3],
      'children': []},
     {'id': 19,
      'name': 'parse_num:while_1 ? [1]',
      'indexes': [],
      'children': []},
     {'id': 20, 'name': 'is_digit', 'indexes': [4], 'children': []},
     {'id': 21,
      'name': 'parse_num:while_1 ? [2]',
      'indexes': [],
      'children': []},
     {'id': 22, 'name': 'is_digit', 'indexes': [], 'children': []}]}]},
 17: {'id': 17,
  'name': 'parse_num',
  'indexes': [],
  'children': [{'id': 18, 'name': 'is_digit', 'indexes': [3], 'children': []},
   {'id': 19,
    'name': 'parse_num:while_1 ? [1]',
    'indexes': [],
    'children': []},
   {'id': 20, 'name': 'is_digit', 'indexes': [4], 'children': []},
   {'id': 21,
    'name': 'parse_num:while_1 ? [2]',
    'indexes': [],
    'children': []},
   {'id': 22, 'name': 'is_digit', 'indexes': [], 'children': []}]},
 18: {'id': 18, 'name': 'is_digit', 'indexes': [3], 'children': []},
 19: {'id': 19,
  'name': 'parse_num:while_1 ? [1]',
  'indexes': [],
  'children': []},
 20: {'id': 20, 'name': 'is_digit', 'indexes': [4], 'children': []},
 21: {'id': 21,
  'name': 'parse_num:while_1 ? [2]',
  'indexes': [],
  'children': []},
 22: {'id': 22, 'name': 'is_digit', 'indexes': [], 'children': []},
 24: {'id': 24,
  'name': 'parse_expr:if_1 = 1#[2, -1]',
  'indexes': [],
  'children': []},
 26: {'id': 26,
  'name': 'parse_expr:if_1 = 0#[3, -1]',
  'indexes': [],
  'children': [{'id': 27,
    'name': 'parse_num',
    'indexes': [],
    'children': [{'id': 28,
      'name': 'is_digit',
      'indexes': [6],
      'children': []},
     {'id': 29,
      'name': 'parse_num:while_1 ? [1]',
      'indexes': [],
      'children': []},
     {'id': 30, 'name': 'is_digit', 'indexes': [7], 'children': []},
     {'id': 31,
      'name': 'parse_num:while_1 ? [2]',
      'indexes': [],
      'children': []},
     {'id': 32, 'name': 'is_digit', 'indexes': [], 'children': []}]}]},
 27: {'id': 27,
  'name': 'parse_num',
  'indexes': [],
  'children': [{'id': 28, 'name': 'is_digit', 'indexes': [6], 'children': []},
   {'id': 29,
    'name': 'parse_num:while_1 ? [1]',
    'indexes': [],
    'children': []},
   {'id': 30, 'name': 'is_digit', 'indexes': [7], 'children': []},
   {'id': 31,
    'name': 'parse_num:while_1 ? [2]',
    'indexes': [],
    'children': []},
   {'id': 32, 'name': 'is_digit', 'indexes': [], 'children': []}]},
 28: {'id': 28, 'name': 'is_digit', 'indexes': [6], 'children': []},
 29: {'id': 29,
  'name': 'parse_num:while_1 ? [1]',
  'indexes': [],
  'children': []},
 30: {'id': 30, 'name': 'is_digit', 'indexes': [7], 'children': []},
 31: {'id': 31,
  'name': 'parse_num:while_1 ? [2]',
  'indexes': [],
  'children': []},
 32: {'id': 32, 'name': 'is_digit', 'indexes': [], 'children': []},
 34: {'id': 34,
  'name': 'parse_expr:if_1 = 3#[4, -1]',
  'indexes': [],
  'children': []},
 36: {'id': 36,
  'name': 'parse_expr:if_1 = 1#[4, -1]',
  'indexes': [],
  'children': []},
 38: {'id': 38,
  'name': 'parse_expr:if_1 = 0#[5, -1]',
  'indexes': [],
  'children': [{'id': 39,
    'name': 'parse_num',
    'indexes': [],
    'children': [{'id': 40,
      'name': 'is_digit',
      'indexes': [10],
      'children': []},
     {'id': 41,
      'name': 'parse_num:while_1 ? [1]',
      'indexes': [],
      'children': []},
     {'id': 42, 'name': 'is_digit', 'indexes': [], 'children': []}]}]},
 39: {'id': 39,
  'name': 'parse_num',
  'indexes': [],
  'children': [{'id': 40, 'name': 'is_digit', 'indexes': [10], 'children': []},
   {'id': 41,
    'name': 'parse_num:while_1 ? [1]',
    'indexes': [],
    'children': []},
   {'id': 42, 'name': 'is_digit', 'indexes': [], 'children': []}]},
 40: {'id': 40, 'name': 'is_digit', 'indexes': [10], 'children': []},
 41: {'id': 41,
  'name': 'parse_num:while_1 ? [1]',
  'indexes': [],
  'children': []},
 42: {'id': 42, 'name': 'is_digit', 'indexes': [], 'children': []},
 44: {'id': 44,
  'name': 'parse_expr:if_1 = 1#[6, -1]',
  'indexes': [],
  'children': []},
 46: {'id': 46,
  'name': 'parse_expr:if_1 = 0#[7, -1]',
  'indexes': [],
  'children': [{'id': 47,
    'name': 'parse_num',
    'indexes': [],
    'children': [{'id': 48,
      'name': 'is_digit',
      'indexes': [12],
      'children': []},
     {'id': 49,
      'name': 'parse_num:while_1 ? [1]',
      'indexes': [],
      'children': []},
     {'id': 50, 'name': 'is_digit', 'indexes': [13], 'children': []},
     {'id': 51,
      'name': 'parse_num:while_1 ? [2]',
      'indexes': [],
      'children': []},
     {'id': 52, 'name': 'is_digit', 'indexes': [14], 'children': []},
     {'id': 53,
      'name': 'parse_num:while_1 ? [3]',
      'indexes': [],
      'children': []}]}]},
 47: {'id': 47,
  'name': 'parse_num',
  'indexes': [],
  'children': [{'id': 48, 'name': 'is_digit', 'indexes': [12], 'children': []},
   {'id': 49,
    'name': 'parse_num:while_1 ? [1]',
    'indexes': [],
    'children': []},
   {'id': 50, 'name': 'is_digit', 'indexes': [13], 'children': []},
   {'id': 51,
    'name': 'parse_num:while_1 ? [2]',
    'indexes': [],
    'children': []},
   {'id': 52, 'name': 'is_digit', 'indexes': [14], 'children': []},
   {'id': 53,
    'name': 'parse_num:while_1 ? [3]',
    'indexes': [],
    'children': []}]},
 48: {'id': 48, 'name': 'is_digit', 'indexes': [12], 'children': []},
 49: {'id': 49,
  'name': 'parse_num:while_1 ? [1]',
  'indexes': [],
  'children': []},
 50: {'id': 50, 'name': 'is_digit', 'indexes': [13], 'children': []},
 51: {'id': 51,
  'name': 'parse_num:while_1 ? [2]',
  'indexes': [],
  'children': []},
 52: {'id': 52, 'name': 'is_digit', 'indexes': [14], 'children': []},
 53: {'id': 53,
  'name': 'parse_num:while_1 ? [3]',
  'indexes': [],
  'children': []}}
In [93]:
In [94]:
Out[94]:
{0: {'id': 0,
  'name': None,
  'children': [{'id': 1,
    'name': 'main',
    'indexes': [],
    'children': [{'id': 2, 'name': '__init__', 'indexes': [], 'children': []},
     {'id': 3,
      'name': 'getValue',
      'indexes': [],
      'children': [{'id': 4,
        'name': 'parseExpression',
        'indexes': [],
        'children': [{'id': 5,
          'name': 'parseAddition',
          'indexes': [],
          'children': [{'id': 6,
            'name': 'parseMultiplication',
            'indexes': [],
            'children': [{'id': 7,
              'name': 'parseParenthesis',
              'indexes': [],
              'children': [{'id': 8,
                'name': 'skipWhitespace',
                'indexes': [],
                'children': [{'id': 9,
                  'name': 'hasNext',
                  'indexes': [],
                  'children': []},
                 {'id': 10,
                  'name': 'skipWhitespace:while_1 ? [1]',
                  'indexes': [],
                  'children': [{'id': 11,
                    'name': 'peek',
                    'indexes': [],
                    'children': []},
                   {'id': 12,
                    'name': 'skipWhitespace:if_1 = 1#[1, -1]',
                    'indexes': [],
                    'children': []}]}]},
               {'id': 13, 'name': 'peek', 'indexes': [], 'children': []},
               {'id': 14,
                'name': 'parseParenthesis:if_1 = 1#[-1]',
                'indexes': [],
                'children': [{'id': 15,
                  'name': 'parseNegative',
                  'indexes': [],
                  'children': [{'id': 16,
                    'name': 'skipWhitespace',
                    'indexes': [],
                    'children': [{'id': 17,
                      'name': 'hasNext',
                      'indexes': [],
                      'children': []},
                     {'id': 18,
                      'name': 'skipWhitespace:while_1 ? [1]',
                      'indexes': [],
                      'children': [{'id': 19,
                        'name': 'peek',
                        'indexes': [],
                        'children': []},
                       {'id': 20,
                        'name': 'skipWhitespace:if_1 = 1#[1, -1]',
                        'indexes': [],
                        'children': []}]}]},
                   {'id': 21, 'name': 'peek', 'indexes': [], 'children': []},
                   {'id': 22,
                    'name': 'parseNegative:if_1 = 1#[-1]',
                    'indexes': [],
                    'children': [{'id': 23,
                      'name': 'parseValue',
                      'indexes': [],
                      'children': [{'id': 24,
                        'name': 'skipWhitespace',
                        'indexes': [],
                        'children': [{'id': 25,
                          'name': 'hasNext',
                          'indexes': [],
                          'children': []},
                         {'id': 26,
                          'name': 'skipWhitespace:while_1 ? [1]',
                          'indexes': [],
                          'children': [{'id': 27,
                            'name': 'peek',
                            'indexes': [],
                            'children': []},
                           {'id': 28,
                            'name': 'skipWhitespace:if_1 = 1#[1, -1]',
                            'indexes': [],
                            'children': []}]}]},
                       {'id': 29,
                        'name': 'peek',
                        'indexes': [],
                        'children': []},
                       {'id': 30,
                        'name': 'parseValue:if_1 = 0#[-1]',
                        'indexes': [],
                        'children': [{'id': 31,
                          'name': 'parseNumber',
                          'indexes': [],
                          'children': [{'id': 32,
                            'name': 'skipWhitespace',
                            'indexes': [],
                            'children': [{'id': 33,
                              'name': 'hasNext',
                              'indexes': [],
                              'children': []},
                             {'id': 34,
                              'name': 'skipWhitespace:while_1 ? [1]',
                              'indexes': [],
                              'children': [{'id': 35,
                                'name': 'peek',
                                'indexes': [],
                                'children': []},
                               {'id': 36,
                                'name': 'skipWhitespace:if_1 = 1#[1, -1]',
                                'indexes': [],
                                'children': []}]}]},
                           {'id': 37,
                            'name': 'hasNext',
                            'indexes': [],
                            'children': []},
                           {'id': 38,
                            'name': 'parseNumber:while_1 ? [1]',
                            'indexes': [0],
                            'children': [{'id': 39,
                              'name': 'peek',
                              'indexes': [],
                              'children': []},
                             {'id': 40,
                              'name': 'parseNumber:if_1 = 1#[1, -1]',
                              'indexes': [],
                              'children': []}]},
                           {'id': 41,
                            'name': 'hasNext',
                            'indexes': [],
                            'children': []},
                           {'id': 42,
                            'name': 'parseNumber:while_1 ? [2]',
                            'indexes': [1],
                            'children': [{'id': 43,
                              'name': 'peek',
                              'indexes': [],
                              'children': []},
                             {'id': 44,
                              'name': 'parseNumber:if_1 = 1#[2, -1]',
                              'indexes': [],
                              'children': []}]},
                           {'id': 45,
                            'name': 'hasNext',
                            'indexes': [],
                            'children': []},
                           {'id': 46,
                            'name': 'parseNumber:while_1 ? [3]',
                            'indexes': [2],
                            'children': [{'id': 47,
                              'name': 'peek',
                              'indexes': [],
                              'children': []},
                             {'id': 48,
                              'name': 'parseNumber:if_1 = 1#[3, -1]',
                              'indexes': [],
                              'children': []}]},
                           {'id': 49,
                            'name': 'hasNext',
                            'indexes': [],
                            'children': []}]}]}]}]}]}]}]},
             {'id': 50,
              'name': 'parseMultiplication:while_1 ? [1]',
              'indexes': [],
              'children': [{'id': 51,
                'name': 'skipWhitespace',
                'indexes': [],
                'children': [{'id': 52,
                  'name': 'hasNext',
                  'indexes': [],
                  'children': []}]},
               {'id': 53, 'name': 'peek', 'indexes': [], 'children': []},
               {'id': 54,
                'name': 'parseMultiplication:if_1 = 2#[1, -1]',
                'indexes': [],
                'children': []}]}]},
           {'id': 55,
            'name': 'parseAddition:while_1 ? [1]',
            'indexes': [],
            'children': [{'id': 56,
              'name': 'skipWhitespace',
              'indexes': [],
              'children': [{'id': 57,
                'name': 'hasNext',
                'indexes': [],
                'children': []}]},
             {'id': 58, 'name': 'peek', 'indexes': [], 'children': []},
             {'id': 59,
              'name': 'parseAddition:if_1 = 2#[1, -1]',
              'indexes': [],
              'children': []}]}]}]},
       {'id': 60,
        'name': 'skipWhitespace',
        'indexes': [],
        'children': [{'id': 61,
          'name': 'hasNext',
          'indexes': [],
          'children': []}]},
       {'id': 62, 'name': 'hasNext', 'indexes': [], 'children': []}]}]}],
  'indexes': []},
 1: {'id': 1,
  'name': 'main',
  'indexes': [],
  'children': [{'id': 2, 'name': '__init__', 'indexes': [], 'children': []},
   {'id': 3,
    'name': 'getValue',
    'indexes': [],
    'children': [{'id': 4,
      'name': 'parseExpression',
      'indexes': [],
      'children': [{'id': 5,
        'name': 'parseAddition',
        'indexes': [],
        'children': [{'id': 6,
          'name': 'parseMultiplication',
          'indexes': [],
          'children': [{'id': 7,
            'name': 'parseParenthesis',
            'indexes': [],
            'children': [{'id': 8,
              'name': 'skipWhitespace',
              'indexes': [],
              'children': [{'id': 9,
                'name': 'hasNext',
                'indexes': [],
                'children': []},
               {'id': 10,
                'name': 'skipWhitespace:while_1 ? [1]',
                'indexes': [],
                'children': [{'id': 11,
                  'name': 'peek',
                  'indexes': [],
                  'children': []},
                 {'id': 12,
                  'name': 'skipWhitespace:if_1 = 1#[1, -1]',
                  'indexes': [],
                  'children': []}]}]},
             {'id': 13, 'name': 'peek', 'indexes': [], 'children': []},
             {'id': 14,
              'name': 'parseParenthesis:if_1 = 1#[-1]',
              'indexes': [],
              'children': [{'id': 15,
                'name': 'parseNegative',
                'indexes': [],
                'children': [{'id': 16,
                  'name': 'skipWhitespace',
                  'indexes': [],
                  'children': [{'id': 17,
                    'name': 'hasNext',
                    'indexes': [],
                    'children': []},
                   {'id': 18,
                    'name': 'skipWhitespace:while_1 ? [1]',
                    'indexes': [],
                    'children': [{'id': 19,
                      'name': 'peek',
                      'indexes': [],
                      'children': []},
                     {'id': 20,
                      'name': 'skipWhitespace:if_1 = 1#[1, -1]',
                      'indexes': [],
                      'children': []}]}]},
                 {'id': 21, 'name': 'peek', 'indexes': [], 'children': []},
                 {'id': 22,
                  'name': 'parseNegative:if_1 = 1#[-1]',
                  'indexes': [],
                  'children': [{'id': 23,
                    'name': 'parseValue',
                    'indexes': [],
                    'children': [{'id': 24,
                      'name': 'skipWhitespace',
                      'indexes': [],
                      'children': [{'id': 25,
                        'name': 'hasNext',
                        'indexes': [],
                        'children': []},
                       {'id': 26,
                        'name': 'skipWhitespace:while_1 ? [1]',
                        'indexes': [],
                        'children': [{'id': 27,
                          'name': 'peek',
                          'indexes': [],
                          'children': []},
                         {'id': 28,
                          'name': 'skipWhitespace:if_1 = 1#[1, -1]',
                          'indexes': [],
                          'children': []}]}]},
                     {'id': 29, 'name': 'peek', 'indexes': [], 'children': []},
                     {'id': 30,
                      'name': 'parseValue:if_1 = 0#[-1]',
                      'indexes': [],
                      'children': [{'id': 31,
                        'name': 'parseNumber',
                        'indexes': [],
                        'children': [{'id': 32,
                          'name': 'skipWhitespace',
                          'indexes': [],
                          'children': [{'id': 33,
                            'name': 'hasNext',
                            'indexes': [],
                            'children': []},
                           {'id': 34,
                            'name': 'skipWhitespace:while_1 ? [1]',
                            'indexes': [],
                            'children': [{'id': 35,
                              'name': 'peek',
                              'indexes': [],
                              'children': []},
                             {'id': 36,
                              'name': 'skipWhitespace:if_1 = 1#[1, -1]',
                              'indexes': [],
                              'children': []}]}]},
                         {'id': 37,
                          'name': 'hasNext',
                          'indexes': [],
                          'children': []},
                         {'id': 38,
                          'name': 'parseNumber:while_1 ? [1]',
                          'indexes': [0],
                          'children': [{'id': 39,
                            'name': 'peek',
                            'indexes': [],
                            'children': []},
                           {'id': 40,
                            'name': 'parseNumber:if_1 = 1#[1, -1]',
                            'indexes': [],
                            'children': []}]},
                         {'id': 41,
                          'name': 'hasNext',
                          'indexes': [],
                          'children': []},
                         {'id': 42,
                          'name': 'parseNumber:while_1 ? [2]',
                          'indexes': [1],
                          'children': [{'id': 43,
                            'name': 'peek',
                            'indexes': [],
                            'children': []},
                           {'id': 44,
                            'name': 'parseNumber:if_1 = 1#[2, -1]',
                            'indexes': [],
                            'children': []}]},
                         {'id': 45,
                          'name': 'hasNext',
                          'indexes': [],
                          'children': []},
                         {'id': 46,
                          'name': 'parseNumber:while_1 ? [3]',
                          'indexes': [2],
                          'children': [{'id': 47,
                            'name': 'peek',
                            'indexes': [],
                            'children': []},
                           {'id': 48,
                            'name': 'parseNumber:if_1 = 1#[3, -1]',
                            'indexes': [],
                            'children': []}]},
                         {'id': 49,
                          'name': 'hasNext',
                          'indexes': [],
                          'children': []}]}]}]}]}]}]}]},
           {'id': 50,
            'name': 'parseMultiplication:while_1 ? [1]',
            'indexes': [],
            'children': [{'id': 51,
              'name': 'skipWhitespace',
              'indexes': [],
              'children': [{'id': 52,
                'name': 'hasNext',
                'indexes': [],
                'children': []}]},
             {'id': 53, 'name': 'peek', 'indexes': [], 'children': []},
             {'id': 54,
              'name': 'parseMultiplication:if_1 = 2#[1, -1]',
              'indexes': [],
              'children': []}]}]},
         {'id': 55,
          'name': 'parseAddition:while_1 ? [1]',
          'indexes': [],
          'children': [{'id': 56,
            'name': 'skipWhitespace',
            'indexes': [],
            'children': [{'id': 57,
              'name': 'hasNext',
              'indexes': [],
              'children': []}]},
           {'id': 58, 'name': 'peek', 'indexes': [], 'children': []},
           {'id': 59,
            'name': 'parseAddition:if_1 = 2#[1, -1]',
            'indexes': [],
            'children': []}]}]}]},
     {'id': 60,
      'name': 'skipWhitespace',
      'indexes': [],
      'children': [{'id': 61,
        'name': 'hasNext',
        'indexes': [],
        'children': []}]},
     {'id': 62, 'name': 'hasNext', 'indexes': [], 'children': []}]}]},
 2: {'id': 2, 'name': '__init__', 'indexes': [], 'children': []},
 3: {'id': 3,
  'name': 'getValue',
  'indexes': [],
  'children': [{'id': 4,
    'name': 'parseExpression',
    'indexes': [],
    'children': [{'id': 5,
      'name': 'parseAddition',
      'indexes': [],
      'children': [{'id': 6,
        'name': 'parseMultiplication',
        'indexes': [],
        'children': [{'id': 7,
          'name': 'parseParenthesis',
          'indexes': [],
          'children': [{'id': 8,
            'name': 'skipWhitespace',
            'indexes': [],
            'children': [{'id': 9,
              'name': 'hasNext',
              'indexes': [],
              'children': []},
             {'id': 10,
              'name': 'skipWhitespace:while_1 ? [1]',
              'indexes': [],
              'children': [{'id': 11,
                'name': 'peek',
                'indexes': [],
                'children': []},
               {'id': 12,
                'name': 'skipWhitespace:if_1 = 1#[1, -1]',
                'indexes': [],
                'children': []}]}]},
           {'id': 13, 'name': 'peek', 'indexes': [], 'children': []},
           {'id': 14,
            'name': 'parseParenthesis:if_1 = 1#[-1]',
            'indexes': [],
            'children': [{'id': 15,
              'name': 'parseNegative',
              'indexes': [],
              'children': [{'id': 16,
                'name': 'skipWhitespace',
                'indexes': [],
                'children': [{'id': 17,
                  'name': 'hasNext',
                  'indexes': [],
                  'children': []},
                 {'id': 18,
                  'name': 'skipWhitespace:while_1 ? [1]',
                  'indexes': [],
                  'children': [{'id': 19,
                    'name': 'peek',
                    'indexes': [],
                    'children': []},
                   {'id': 20,
                    'name': 'skipWhitespace:if_1 = 1#[1, -1]',
                    'indexes': [],
                    'children': []}]}]},
               {'id': 21, 'name': 'peek', 'indexes': [], 'children': []},
               {'id': 22,
                'name': 'parseNegative:if_1 = 1#[-1]',
                'indexes': [],
                'children': [{'id': 23,
                  'name': 'parseValue',
                  'indexes': [],
                  'children': [{'id': 24,
                    'name': 'skipWhitespace',
                    'indexes': [],
                    'children': [{'id': 25,
                      'name': 'hasNext',
                      'indexes': [],
                      'children': []},
                     {'id': 26,
                      'name': 'skipWhitespace:while_1 ? [1]',
                      'indexes': [],
                      'children': [{'id': 27,
                        'name': 'peek',
                        'indexes': [],
                        'children': []},
                       {'id': 28,
                        'name': 'skipWhitespace:if_1 = 1#[1, -1]',
                        'indexes': [],
                        'children': []}]}]},
                   {'id': 29, 'name': 'peek', 'indexes': [], 'children': []},
                   {'id': 30,
                    'name': 'parseValue:if_1 = 0#[-1]',
                    'indexes': [],
                    'children': [{'id': 31,
                      'name': 'parseNumber',
                      'indexes': [],
                      'children': [{'id': 32,
                        'name': 'skipWhitespace',
                        'indexes': [],
                        'children': [{'id': 33,
                          'name': 'hasNext',
                          'indexes': [],
                          'children': []},
                         {'id': 34,
                          'name': 'skipWhitespace:while_1 ? [1]',
                          'indexes': [],
                          'children': [{'id': 35,
                            'name': 'peek',
                            'indexes': [],
                            'children': []},
                           {'id': 36,
                            'name': 'skipWhitespace:if_1 = 1#[1, -1]',
                            'indexes': [],
                            'children': []}]}]},
                       {'id': 37,
                        'name': 'hasNext',
                        'indexes': [],
                        'children': []},
                       {'id': 38,
                        'name': 'parseNumber:while_1 ? [1]',
                        'indexes': [0],
                        'children': [{'id': 39,
                          'name': 'peek',
                          'indexes': [],
                          'children': []},
                         {'id': 40,
                          'name': 'parseNumber:if_1 = 1#[1, -1]',
                          'indexes': [],
                          'children': []}]},
                       {'id': 41,
                        'name': 'hasNext',
                        'indexes': [],
                        'children': []},
                       {'id': 42,
                        'name': 'parseNumber:while_1 ? [2]',
                        'indexes': [1],
                        'children': [{'id': 43,
                          'name': 'peek',
                          'indexes': [],
                          'children': []},
                         {'id': 44,
                          'name': 'parseNumber:if_1 = 1#[2, -1]',
                          'indexes': [],
                          'children': []}]},
                       {'id': 45,
                        'name': 'hasNext',
                        'indexes': [],
                        'children': []},
                       {'id': 46,
                        'name': 'parseNumber:while_1 ? [3]',
                        'indexes': [2],
                        'children': [{'id': 47,
                          'name': 'peek',
                          'indexes': [],
                          'children': []},
                         {'id': 48,
                          'name': 'parseNumber:if_1 = 1#[3, -1]',
                          'indexes': [],
                          'children': []}]},
                       {'id': 49,
                        'name': 'hasNext',
                        'indexes': [],
                        'children': []}]}]}]}]}]}]}]},
         {'id': 50,
          'name': 'parseMultiplication:while_1 ? [1]',
          'indexes': [],
          'children': [{'id': 51,
            'name': 'skipWhitespace',
            'indexes': [],
            'children': [{'id': 52,
              'name': 'hasNext',
              'indexes': [],
              'children': []}]},
           {'id': 53, 'name': 'peek', 'indexes': [], 'children': []},
           {'id': 54,
            'name': 'parseMultiplication:if_1 = 2#[1, -1]',
            'indexes': [],
            'children': []}]}]},
       {'id': 55,
        'name': 'parseAddition:while_1 ? [1]',
        'indexes': [],
        'children': [{'id': 56,
          'name': 'skipWhitespace',
          'indexes': [],
          'children': [{'id': 57,
            'name': 'hasNext',
            'indexes': [],
            'children': []}]},
         {'id': 58, 'name': 'peek', 'indexes': [], 'children': []},
         {'id': 59,
          'name': 'parseAddition:if_1 = 2#[1, -1]',
          'indexes': [],
          'children': []}]}]}]},
   {'id': 60,
    'name': 'skipWhitespace',
    'indexes': [],
    'children': [{'id': 61,
      'name': 'hasNext',
      'indexes': [],
      'children': []}]},
   {'id': 62, 'name': 'hasNext', 'indexes': [], 'children': []}]},
 4: {'id': 4,
  'name': 'parseExpression',
  'indexes': [],
  'children': [{'id': 5,
    'name': 'parseAddition',
    'indexes': [],
    'children': [{'id': 6,
      'name': 'parseMultiplication',
      'indexes': [],
      'children': [{'id': 7,
        'name': 'parseParenthesis',
        'indexes': [],
        'children': [{'id': 8,
          'name': 'skipWhitespace',
          'indexes': [],
          'children': [{'id': 9,
            'name': 'hasNext',
            'indexes': [],
            'children': []},
           {'id': 10,
            'name': 'skipWhitespace:while_1 ? [1]',
            'indexes': [],
            'children': [{'id': 11,
              'name': 'peek',
              'indexes': [],
              'children': []},
             {'id': 12,
              'name': 'skipWhitespace:if_1 = 1#[1, -1]',
              'indexes': [],
              'children': []}]}]},
         {'id': 13, 'name': 'peek', 'indexes': [], 'children': []},
         {'id': 14,
          'name': 'parseParenthesis:if_1 = 1#[-1]',
          'indexes': [],
          'children': [{'id': 15,
            'name': 'parseNegative',
            'indexes': [],
            'children': [{'id': 16,
              'name': 'skipWhitespace',
              'indexes': [],
              'children': [{'id': 17,
                'name': 'hasNext',
                'indexes': [],
                'children': []},
               {'id': 18,
                'name': 'skipWhitespace:while_1 ? [1]',
                'indexes': [],
                'children': [{'id': 19,
                  'name': 'peek',
                  'indexes': [],
                  'children': []},
                 {'id': 20,
                  'name': 'skipWhitespace:if_1 = 1#[1, -1]',
                  'indexes': [],
                  'children': []}]}]},
             {'id': 21, 'name': 'peek', 'indexes': [], 'children': []},
             {'id': 22,
              'name': 'parseNegative:if_1 = 1#[-1]',
              'indexes': [],
              'children': [{'id': 23,
                'name': 'parseValue',
                'indexes': [],
                'children': [{'id': 24,
                  'name': 'skipWhitespace',
                  'indexes': [],
                  'children': [{'id': 25,
                    'name': 'hasNext',
                    'indexes': [],
                    'children': []},
                   {'id': 26,
                    'name': 'skipWhitespace:while_1 ? [1]',
                    'indexes': [],
                    'children': [{'id': 27,
                      'name': 'peek',
                      'indexes': [],
                      'children': []},
                     {'id': 28,
                      'name': 'skipWhitespace:if_1 = 1#[1, -1]',
                      'indexes': [],
                      'children': []}]}]},
                 {'id': 29, 'name': 'peek', 'indexes': [], 'children': []},
                 {'id': 30,
                  'name': 'parseValue:if_1 = 0#[-1]',
                  'indexes': [],
                  'children': [{'id': 31,
                    'name': 'parseNumber',
                    'indexes': [],
                    'children': [{'id': 32,
                      'name': 'skipWhitespace',
                      'indexes': [],
                      'children': [{'id': 33,
                        'name': 'hasNext',
                        'indexes': [],
                        'children': []},
                       {'id': 34,
                        'name': 'skipWhitespace:while_1 ? [1]',
                        'indexes': [],
                        'children': [{'id': 35,
                          'name': 'peek',
                          'indexes': [],
                          'children': []},
                         {'id': 36,
                          'name': 'skipWhitespace:if_1 = 1#[1, -1]',
                          'indexes': [],
                          'children': []}]}]},
                     {'id': 37,
                      'name': 'hasNext',
                      'indexes': [],
                      'children': []},
                     {'id': 38,
                      'name': 'parseNumber:while_1 ? [1]',
                      'indexes': [0],
                      'children': [{'id': 39,
                        'name': 'peek',
                        'indexes': [],
                        'children': []},
                       {'id': 40,
                        'name': 'parseNumber:if_1 = 1#[1, -1]',
                        'indexes': [],
                        'children': []}]},
                     {'id': 41,
                      'name': 'hasNext',
                      'indexes': [],
                      'children': []},
                     {'id': 42,
                      'name': 'parseNumber:while_1 ? [2]',
                      'indexes': [1],
                      'children': [{'id': 43,
                        'name': 'peek',
                        'indexes': [],
                        'children': []},
                       {'id': 44,
                        'name': 'parseNumber:if_1 = 1#[2, -1]',
                        'indexes': [],
                        'children': []}]},
                     {'id': 45,
                      'name': 'hasNext',
                      'indexes': [],
                      'children': []},
                     {'id': 46,
                      'name': 'parseNumber:while_1 ? [3]',
                      'indexes': [2],
                      'children': [{'id': 47,
                        'name': 'peek',
                        'indexes': [],
                        'children': []},
                       {'id': 48,
                        'name': 'parseNumber:if_1 = 1#[3, -1]',
                        'indexes': [],
                        'children': []}]},
                     {'id': 49,
                      'name': 'hasNext',
                      'indexes': [],
                      'children': []}]}]}]}]}]}]}]},
       {'id': 50,
        'name': 'parseMultiplication:while_1 ? [1]',
        'indexes': [],
        'children': [{'id': 51,
          'name': 'skipWhitespace',
          'indexes': [],
          'children': [{'id': 52,
            'name': 'hasNext',
            'indexes': [],
            'children': []}]},
         {'id': 53, 'name': 'peek', 'indexes': [], 'children': []},
         {'id': 54,
          'name': 'parseMultiplication:if_1 = 2#[1, -1]',
          'indexes': [],
          'children': []}]}]},
     {'id': 55,
      'name': 'parseAddition:while_1 ? [1]',
      'indexes': [],
      'children': [{'id': 56,
        'name': 'skipWhitespace',
        'indexes': [],
        'children': [{'id': 57,
          'name': 'hasNext',
          'indexes': [],
          'children': []}]},
       {'id': 58, 'name': 'peek', 'indexes': [], 'children': []},
       {'id': 59,
        'name': 'parseAddition:if_1 = 2#[1, -1]',
        'indexes': [],
        'children': []}]}]}]},
 60: {'id': 60,
  'name': 'skipWhitespace',
  'indexes': [],
  'children': [{'id': 61, 'name': 'hasNext', 'indexes': [], 'children': []}]},
 62: {'id': 62, 'name': 'hasNext', 'indexes': [], 'children': []},
 5: {'id': 5,
  'name': 'parseAddition',
  'indexes': [],
  'children': [{'id': 6,
    'name': 'parseMultiplication',
    'indexes': [],
    'children': [{'id': 7,
      'name': 'parseParenthesis',
      'indexes': [],
      'children': [{'id': 8,
        'name': 'skipWhitespace',
        'indexes': [],
        'children': [{'id': 9,
          'name': 'hasNext',
          'indexes': [],
          'children': []},
         {'id': 10,
          'name': 'skipWhitespace:while_1 ? [1]',
          'indexes': [],
          'children': [{'id': 11,
            'name': 'peek',
            'indexes': [],
            'children': []},
           {'id': 12,
            'name': 'skipWhitespace:if_1 = 1#[1, -1]',
            'indexes': [],
            'children': []}]}]},
       {'id': 13, 'name': 'peek', 'indexes': [], 'children': []},
       {'id': 14,
        'name': 'parseParenthesis:if_1 = 1#[-1]',
        'indexes': [],
        'children': [{'id': 15,
          'name': 'parseNegative',
          'indexes': [],
          'children': [{'id': 16,
            'name': 'skipWhitespace',
            'indexes': [],
            'children': [{'id': 17,
              'name': 'hasNext',
              'indexes': [],
              'children': []},
             {'id': 18,
              'name': 'skipWhitespace:while_1 ? [1]',
              'indexes': [],
              'children': [{'id': 19,
                'name': 'peek',
                'indexes': [],
                'children': []},
               {'id': 20,
                'name': 'skipWhitespace:if_1 = 1#[1, -1]',
                'indexes': [],
                'children': []}]}]},
           {'id': 21, 'name': 'peek', 'indexes': [], 'children': []},
           {'id': 22,
            'name': 'parseNegative:if_1 = 1#[-1]',
            'indexes': [],
            'children': [{'id': 23,
              'name': 'parseValue',
              'indexes': [],
              'children': [{'id': 24,
                'name': 'skipWhitespace',
                'indexes': [],
                'children': [{'id': 25,
                  'name': 'hasNext',
                  'indexes': [],
                  'children': []},
                 {'id': 26,
                  'name': 'skipWhitespace:while_1 ? [1]',
                  'indexes': [],
                  'children': [{'id': 27,
                    'name': 'peek',
                    'indexes': [],
                    'children': []},
                   {'id': 28,
                    'name': 'skipWhitespace:if_1 = 1#[1, -1]',
                    'indexes': [],
                    'children': []}]}]},
               {'id': 29, 'name': 'peek', 'indexes': [], 'children': []},
               {'id': 30,
                'name': 'parseValue:if_1 = 0#[-1]',
                'indexes': [],
                'children': [{'id': 31,
                  'name': 'parseNumber',
                  'indexes': [],
                  'children': [{'id': 32,
                    'name': 'skipWhitespace',
                    'indexes': [],
                    'children': [{'id': 33,
                      'name': 'hasNext',
                      'indexes': [],
                      'children': []},
                     {'id': 34,
                      'name': 'skipWhitespace:while_1 ? [1]',
                      'indexes': [],
                      'children': [{'id': 35,
                        'name': 'peek',
                        'indexes': [],
                        'children': []},
                       {'id': 36,
                        'name': 'skipWhitespace:if_1 = 1#[1, -1]',
                        'indexes': [],
                        'children': []}]}]},
                   {'id': 37,
                    'name': 'hasNext',
                    'indexes': [],
                    'children': []},
                   {'id': 38,
                    'name': 'parseNumber:while_1 ? [1]',
                    'indexes': [0],
                    'children': [{'id': 39,
                      'name': 'peek',
                      'indexes': [],
                      'children': []},
                     {'id': 40,
                      'name': 'parseNumber:if_1 = 1#[1, -1]',
                      'indexes': [],
                      'children': []}]},
                   {'id': 41,
                    'name': 'hasNext',
                    'indexes': [],
                    'children': []},
                   {'id': 42,
                    'name': 'parseNumber:while_1 ? [2]',
                    'indexes': [1],
                    'children': [{'id': 43,
                      'name': 'peek',
                      'indexes': [],
                      'children': []},
                     {'id': 44,
                      'name': 'parseNumber:if_1 = 1#[2, -1]',
                      'indexes': [],
                      'children': []}]},
                   {'id': 45,
                    'name': 'hasNext',
                    'indexes': [],
                    'children': []},
                   {'id': 46,
                    'name': 'parseNumber:while_1 ? [3]',
                    'indexes': [2],
                    'children': [{'id': 47,
                      'name': 'peek',
                      'indexes': [],
                      'children': []},
                     {'id': 48,
                      'name': 'parseNumber:if_1 = 1#[3, -1]',
                      'indexes': [],
                      'children': []}]},
                   {'id': 49,
                    'name': 'hasNext',
                    'indexes': [],
                    'children': []}]}]}]}]}]}]}]},
     {'id': 50,
      'name': 'parseMultiplication:while_1 ? [1]',
      'indexes': [],
      'children': [{'id': 51,
        'name': 'skipWhitespace',
        'indexes': [],
        'children': [{'id': 52,
          'name': 'hasNext',
          'indexes': [],
          'children': []}]},
       {'id': 53, 'name': 'peek', 'indexes': [], 'children': []},
       {'id': 54,
        'name': 'parseMultiplication:if_1 = 2#[1, -1]',
        'indexes': [],
        'children': []}]}]},
   {'id': 55,
    'name': 'parseAddition:while_1 ? [1]',
    'indexes': [],
    'children': [{'id': 56,
      'name': 'skipWhitespace',
      'indexes': [],
      'children': [{'id': 57,
        'name': 'hasNext',
        'indexes': [],
        'children': []}]},
     {'id': 58, 'name': 'peek', 'indexes': [], 'children': []},
     {'id': 59,
      'name': 'parseAddition:if_1 = 2#[1, -1]',
      'indexes': [],
      'children': []}]}]},
 6: {'id': 6,
  'name': 'parseMultiplication',
  'indexes': [],
  'children': [{'id': 7,
    'name': 'parseParenthesis',
    'indexes': [],
    'children': [{'id': 8,
      'name': 'skipWhitespace',
      'indexes': [],
      'children': [{'id': 9, 'name': 'hasNext', 'indexes': [], 'children': []},
       {'id': 10,
        'name': 'skipWhitespace:while_1 ? [1]',
        'indexes': [],
        'children': [{'id': 11, 'name': 'peek', 'indexes': [], 'children': []},
         {'id': 12,
          'name': 'skipWhitespace:if_1 = 1#[1, -1]',
          'indexes': [],
          'children': []}]}]},
     {'id': 13, 'name': 'peek', 'indexes': [], 'children': []},
     {'id': 14,
      'name': 'parseParenthesis:if_1 = 1#[-1]',
      'indexes': [],
      'children': [{'id': 15,
        'name': 'parseNegative',
        'indexes': [],
        'children': [{'id': 16,
          'name': 'skipWhitespace',
          'indexes': [],
          'children': [{'id': 17,
            'name': 'hasNext',
            'indexes': [],
            'children': []},
           {'id': 18,
            'name': 'skipWhitespace:while_1 ? [1]',
            'indexes': [],
            'children': [{'id': 19,
              'name': 'peek',
              'indexes': [],
              'children': []},
             {'id': 20,
              'name': 'skipWhitespace:if_1 = 1#[1, -1]',
              'indexes': [],
              'children': []}]}]},
         {'id': 21, 'name': 'peek', 'indexes': [], 'children': []},
         {'id': 22,
          'name': 'parseNegative:if_1 = 1#[-1]',
          'indexes': [],
          'children': [{'id': 23,
            'name': 'parseValue',
            'indexes': [],
            'children': [{'id': 24,
              'name': 'skipWhitespace',
              'indexes': [],
              'children': [{'id': 25,
                'name': 'hasNext',
                'indexes': [],
                'children': []},
               {'id': 26,
                'name': 'skipWhitespace:while_1 ? [1]',
                'indexes': [],
                'children': [{'id': 27,
                  'name': 'peek',
                  'indexes': [],
                  'children': []},
                 {'id': 28,
                  'name': 'skipWhitespace:if_1 = 1#[1, -1]',
                  'indexes': [],
                  'children': []}]}]},
             {'id': 29, 'name': 'peek', 'indexes': [], 'children': []},
             {'id': 30,
              'name': 'parseValue:if_1 = 0#[-1]',
              'indexes': [],
              'children': [{'id': 31,
                'name': 'parseNumber',
                'indexes': [],
                'children': [{'id': 32,
                  'name': 'skipWhitespace',
                  'indexes': [],
                  'children': [{'id': 33,
                    'name': 'hasNext',
                    'indexes': [],
                    'children': []},
                   {'id': 34,
                    'name': 'skipWhitespace:while_1 ? [1]',
                    'indexes': [],
                    'children': [{'id': 35,
                      'name': 'peek',
                      'indexes': [],
                      'children': []},
                     {'id': 36,
                      'name': 'skipWhitespace:if_1 = 1#[1, -1]',
                      'indexes': [],
                      'children': []}]}]},
                 {'id': 37, 'name': 'hasNext', 'indexes': [], 'children': []},
                 {'id': 38,
                  'name': 'parseNumber:while_1 ? [1]',
                  'indexes': [0],
                  'children': [{'id': 39,
                    'name': 'peek',
                    'indexes': [],
                    'children': []},
                   {'id': 40,
                    'name': 'parseNumber:if_1 = 1#[1, -1]',
                    'indexes': [],
                    'children': []}]},
                 {'id': 41, 'name': 'hasNext', 'indexes': [], 'children': []},
                 {'id': 42,
                  'name': 'parseNumber:while_1 ? [2]',
                  'indexes': [1],
                  'children': [{'id': 43,
                    'name': 'peek',
                    'indexes': [],
                    'children': []},
                   {'id': 44,
                    'name': 'parseNumber:if_1 = 1#[2, -1]',
                    'indexes': [],
                    'children': []}]},
                 {'id': 45, 'name': 'hasNext', 'indexes': [], 'children': []},
                 {'id': 46,
                  'name': 'parseNumber:while_1 ? [3]',
                  'indexes': [2],
                  'children': [{'id': 47,
                    'name': 'peek',
                    'indexes': [],
                    'children': []},
                   {'id': 48,
                    'name': 'parseNumber:if_1 = 1#[3, -1]',
                    'indexes': [],
                    'children': []}]},
                 {'id': 49,
                  'name': 'hasNext',
                  'indexes': [],
                  'children': []}]}]}]}]}]}]}]},
   {'id': 50,
    'name': 'parseMultiplication:while_1 ? [1]',
    'indexes': [],
    'children': [{'id': 51,
      'name': 'skipWhitespace',
      'indexes': [],
      'children': [{'id': 52,
        'name': 'hasNext',
        'indexes': [],
        'children': []}]},
     {'id': 53, 'name': 'peek', 'indexes': [], 'children': []},
     {'id': 54,
      'name': 'parseMultiplication:if_1 = 2#[1, -1]',
      'indexes': [],
      'children': []}]}]},
 55: {'id': 55,
  'name': 'parseAddition:while_1 ? [1]',
  'indexes': [],
  'children': [{'id': 56,
    'name': 'skipWhitespace',
    'indexes': [],
    'children': [{'id': 57,
      'name': 'hasNext',
      'indexes': [],
      'children': []}]},
   {'id': 58, 'name': 'peek', 'indexes': [], 'children': []},
   {'id': 59,
    'name': 'parseAddition:if_1 = 2#[1, -1]',
    'indexes': [],
    'children': []}]},
 7: {'id': 7,
  'name': 'parseParenthesis',
  'indexes': [],
  'children': [{'id': 8,
    'name': 'skipWhitespace',
    'indexes': [],
    'children': [{'id': 9, 'name': 'hasNext', 'indexes': [], 'children': []},
     {'id': 10,
      'name': 'skipWhitespace:while_1 ? [1]',
      'indexes': [],
      'children': [{'id': 11, 'name': 'peek', 'indexes': [], 'children': []},
       {'id': 12,
        'name': 'skipWhitespace:if_1 = 1#[1, -1]',
        'indexes': [],
        'children': []}]}]},
   {'id': 13, 'name': 'peek', 'indexes': [], 'children': []},
   {'id': 14,
    'name': 'parseParenthesis:if_1 = 1#[-1]',
    'indexes': [],
    'children': [{'id': 15,
      'name': 'parseNegative',
      'indexes': [],
      'children': [{'id': 16,
        'name': 'skipWhitespace',
        'indexes': [],
        'children': [{'id': 17,
          'name': 'hasNext',
          'indexes': [],
          'children': []},
         {'id': 18,
          'name': 'skipWhitespace:while_1 ? [1]',
          'indexes': [],
          'children': [{'id': 19,
            'name': 'peek',
            'indexes': [],
            'children': []},
           {'id': 20,
            'name': 'skipWhitespace:if_1 = 1#[1, -1]',
            'indexes': [],
            'children': []}]}]},
       {'id': 21, 'name': 'peek', 'indexes': [], 'children': []},
       {'id': 22,
        'name': 'parseNegative:if_1 = 1#[-1]',
        'indexes': [],
        'children': [{'id': 23,
          'name': 'parseValue',
          'indexes': [],
          'children': [{'id': 24,
            'name': 'skipWhitespace',
            'indexes': [],
            'children': [{'id': 25,
              'name': 'hasNext',
              'indexes': [],
              'children': []},
             {'id': 26,
              'name': 'skipWhitespace:while_1 ? [1]',
              'indexes': [],
              'children': [{'id': 27,
                'name': 'peek',
                'indexes': [],
                'children': []},
               {'id': 28,
                'name': 'skipWhitespace:if_1 = 1#[1, -1]',
                'indexes': [],
                'children': []}]}]},
           {'id': 29, 'name': 'peek', 'indexes': [], 'children': []},
           {'id': 30,
            'name': 'parseValue:if_1 = 0#[-1]',
            'indexes': [],
            'children': [{'id': 31,
              'name': 'parseNumber',
              'indexes': [],
              'children': [{'id': 32,
                'name': 'skipWhitespace',
                'indexes': [],
                'children': [{'id': 33,
                  'name': 'hasNext',
                  'indexes': [],
                  'children': []},
                 {'id': 34,
                  'name': 'skipWhitespace:while_1 ? [1]',
                  'indexes': [],
                  'children': [{'id': 35,
                    'name': 'peek',
                    'indexes': [],
                    'children': []},
                   {'id': 36,
                    'name': 'skipWhitespace:if_1 = 1#[1, -1]',
                    'indexes': [],
                    'children': []}]}]},
               {'id': 37, 'name': 'hasNext', 'indexes': [], 'children': []},
               {'id': 38,
                'name': 'parseNumber:while_1 ? [1]',
                'indexes': [0],
                'children': [{'id': 39,
                  'name': 'peek',
                  'indexes': [],
                  'children': []},
                 {'id': 40,
                  'name': 'parseNumber:if_1 = 1#[1, -1]',
                  'indexes': [],
                  'children': []}]},
               {'id': 41, 'name': 'hasNext', 'indexes': [], 'children': []},
               {'id': 42,
                'name': 'parseNumber:while_1 ? [2]',
                'indexes': [1],
                'children': [{'id': 43,
                  'name': 'peek',
                  'indexes': [],
                  'children': []},
                 {'id': 44,
                  'name': 'parseNumber:if_1 = 1#[2, -1]',
                  'indexes': [],
                  'children': []}]},
               {'id': 45, 'name': 'hasNext', 'indexes': [], 'children': []},
               {'id': 46,
                'name': 'parseNumber:while_1 ? [3]',
                'indexes': [2],
                'children': [{'id': 47,
                  'name': 'peek',
                  'indexes': [],
                  'children': []},
                 {'id': 48,
                  'name': 'parseNumber:if_1 = 1#[3, -1]',
                  'indexes': [],
                  'children': []}]},
               {'id': 49,
                'name': 'hasNext',
                'indexes': [],
                'children': []}]}]}]}]}]}]}]},
 50: {'id': 50,
  'name': 'parseMultiplication:while_1 ? [1]',
  'indexes': [],
  'children': [{'id': 51,
    'name': 'skipWhitespace',
    'indexes': [],
    'children': [{'id': 52,
      'name': 'hasNext',
      'indexes': [],
      'children': []}]},
   {'id': 53, 'name': 'peek', 'indexes': [], 'children': []},
   {'id': 54,
    'name': 'parseMultiplication:if_1 = 2#[1, -1]',
    'indexes': [],
    'children': []}]},
 8: {'id': 8,
  'name': 'skipWhitespace',
  'indexes': [],
  'children': [{'id': 9, 'name': 'hasNext', 'indexes': [], 'children': []},
   {'id': 10,
    'name': 'skipWhitespace:while_1 ? [1]',
    'indexes': [],
    'children': [{'id': 11, 'name': 'peek', 'indexes': [], 'children': []},
     {'id': 12,
      'name': 'skipWhitespace:if_1 = 1#[1, -1]',
      'indexes': [],
      'children': []}]}]},
 13: {'id': 13, 'name': 'peek', 'indexes': [], 'children': []},
 14: {'id': 14,
  'name': 'parseParenthesis:if_1 = 1#[-1]',
  'indexes': [],
  'children': [{'id': 15,
    'name': 'parseNegative',
    'indexes': [],
    'children': [{'id': 16,
      'name': 'skipWhitespace',
      'indexes': [],
      'children': [{'id': 17,
        'name': 'hasNext',
        'indexes': [],
        'children': []},
       {'id': 18,
        'name': 'skipWhitespace:while_1 ? [1]',
        'indexes': [],
        'children': [{'id': 19, 'name': 'peek', 'indexes': [], 'children': []},
         {'id': 20,
          'name': 'skipWhitespace:if_1 = 1#[1, -1]',
          'indexes': [],
          'children': []}]}]},
     {'id': 21, 'name': 'peek', 'indexes': [], 'children': []},
     {'id': 22,
      'name': 'parseNegative:if_1 = 1#[-1]',
      'indexes': [],
      'children': [{'id': 23,
        'name': 'parseValue',
        'indexes': [],
        'children': [{'id': 24,
          'name': 'skipWhitespace',
          'indexes': [],
          'children': [{'id': 25,
            'name': 'hasNext',
            'indexes': [],
            'children': []},
           {'id': 26,
            'name': 'skipWhitespace:while_1 ? [1]',
            'indexes': [],
            'children': [{'id': 27,
              'name': 'peek',
              'indexes': [],
              'children': []},
             {'id': 28,
              'name': 'skipWhitespace:if_1 = 1#[1, -1]',
              'indexes': [],
              'children': []}]}]},
         {'id': 29, 'name': 'peek', 'indexes': [], 'children': []},
         {'id': 30,
          'name': 'parseValue:if_1 = 0#[-1]',
          'indexes': [],
          'children': [{'id': 31,
            'name': 'parseNumber',
            'indexes': [],
            'children': [{'id': 32,
              'name': 'skipWhitespace',
              'indexes': [],
              'children': [{'id': 33,
                'name': 'hasNext',
                'indexes': [],
                'children': []},
               {'id': 34,
                'name': 'skipWhitespace:while_1 ? [1]',
                'indexes': [],
                'children': [{'id': 35,
                  'name': 'peek',
                  'indexes': [],
                  'children': []},
                 {'id': 36,
                  'name': 'skipWhitespace:if_1 = 1#[1, -1]',
                  'indexes': [],
                  'children': []}]}]},
             {'id': 37, 'name': 'hasNext', 'indexes': [], 'children': []},
             {'id': 38,
              'name': 'parseNumber:while_1 ? [1]',
              'indexes': [0],
              'children': [{'id': 39,
                'name': 'peek',
                'indexes': [],
                'children': []},
               {'id': 40,
                'name': 'parseNumber:if_1 = 1#[1, -1]',
                'indexes': [],
                'children': []}]},
             {'id': 41, 'name': 'hasNext', 'indexes': [], 'children': []},
             {'id': 42,
              'name': 'parseNumber:while_1 ? [2]',
              'indexes': [1],
              'children': [{'id': 43,
                'name': 'peek',
                'indexes': [],
                'children': []},
               {'id': 44,
                'name': 'parseNumber:if_1 = 1#[2, -1]',
                'indexes': [],
                'children': []}]},
             {'id': 45, 'name': 'hasNext', 'indexes': [], 'children': []},
             {'id': 46,
              'name': 'parseNumber:while_1 ? [3]',
              'indexes': [2],
              'children': [{'id': 47,
                'name': 'peek',
                'indexes': [],
                'children': []},
               {'id': 48,
                'name': 'parseNumber:if_1 = 1#[3, -1]',
                'indexes': [],
                'children': []}]},
             {'id': 49,
              'name': 'hasNext',
              'indexes': [],
              'children': []}]}]}]}]}]}]},
 9: {'id': 9, 'name': 'hasNext', 'indexes': [], 'children': []},
 10: {'id': 10,
  'name': 'skipWhitespace:while_1 ? [1]',
  'indexes': [],
  'children': [{'id': 11, 'name': 'peek', 'indexes': [], 'children': []},
   {'id': 12,
    'name': 'skipWhitespace:if_1 = 1#[1, -1]',
    'indexes': [],
    'children': []}]},
 11: {'id': 11, 'name': 'peek', 'indexes': [], 'children': []},
 12: {'id': 12,
  'name': 'skipWhitespace:if_1 = 1#[1, -1]',
  'indexes': [],
  'children': []},
 15: {'id': 15,
  'name': 'parseNegative',
  'indexes': [],
  'children': [{'id': 16,
    'name': 'skipWhitespace',
    'indexes': [],
    'children': [{'id': 17, 'name': 'hasNext', 'indexes': [], 'children': []},
     {'id': 18,
      'name': 'skipWhitespace:while_1 ? [1]',
      'indexes': [],
      'children': [{'id': 19, 'name': 'peek', 'indexes': [], 'children': []},
       {'id': 20,
        'name': 'skipWhitespace:if_1 = 1#[1, -1]',
        'indexes': [],
        'children': []}]}]},
   {'id': 21, 'name': 'peek', 'indexes': [], 'children': []},
   {'id': 22,
    'name': 'parseNegative:if_1 = 1#[-1]',
    'indexes': [],
    'children': [{'id': 23,
      'name': 'parseValue',
      'indexes': [],
      'children': [{'id': 24,
        'name': 'skipWhitespace',
        'indexes': [],
        'children': [{'id': 25,
          'name': 'hasNext',
          'indexes': [],
          'children': []},
         {'id': 26,
          'name': 'skipWhitespace:while_1 ? [1]',
          'indexes': [],
          'children': [{'id': 27,
            'name': 'peek',
            'indexes': [],
            'children': []},
           {'id': 28,
            'name': 'skipWhitespace:if_1 = 1#[1, -1]',
            'indexes': [],
            'children': []}]}]},
       {'id': 29, 'name': 'peek', 'indexes': [], 'children': []},
       {'id': 30,
        'name': 'parseValue:if_1 = 0#[-1]',
        'indexes': [],
        'children': [{'id': 31,
          'name': 'parseNumber',
          'indexes': [],
          'children': [{'id': 32,
            'name': 'skipWhitespace',
            'indexes': [],
            'children': [{'id': 33,
              'name': 'hasNext',
              'indexes': [],
              'children': []},
             {'id': 34,
              'name': 'skipWhitespace:while_1 ? [1]',
              'indexes': [],
              'children': [{'id': 35,
                'name': 'peek',
                'indexes': [],
                'children': []},
               {'id': 36,
                'name': 'skipWhitespace:if_1 = 1#[1, -1]',
                'indexes': [],
                'children': []}]}]},
           {'id': 37, 'name': 'hasNext', 'indexes': [], 'children': []},
           {'id': 38,
            'name': 'parseNumber:while_1 ? [1]',
            'indexes': [0],
            'children': [{'id': 39,
              'name': 'peek',
              'indexes': [],
              'children': []},
             {'id': 40,
              'name': 'parseNumber:if_1 = 1#[1, -1]',
              'indexes': [],
              'children': []}]},
           {'id': 41, 'name': 'hasNext', 'indexes': [], 'children': []},
           {'id': 42,
            'name': 'parseNumber:while_1 ? [2]',
            'indexes': [1],
            'children': [{'id': 43,
              'name': 'peek',
              'indexes': [],
              'children': []},
             {'id': 44,
              'name': 'parseNumber:if_1 = 1#[2, -1]',
              'indexes': [],
              'children': []}]},
           {'id': 45, 'name': 'hasNext', 'indexes': [], 'children': []},
           {'id': 46,
            'name': 'parseNumber:while_1 ? [3]',
            'indexes': [2],
            'children': [{'id': 47,
              'name': 'peek',
              'indexes': [],
              'children': []},
             {'id': 48,
              'name': 'parseNumber:if_1 = 1#[3, -1]',
              'indexes': [],
              'children': []}]},
           {'id': 49,
            'name': 'hasNext',
            'indexes': [],
            'children': []}]}]}]}]}]},
 16: {'id': 16,
  'name': 'skipWhitespace',
  'indexes': [],
  'children': [{'id': 17, 'name': 'hasNext', 'indexes': [], 'children': []},
   {'id': 18,
    'name': 'skipWhitespace:while_1 ? [1]',
    'indexes': [],
    'children': [{'id': 19, 'name': 'peek', 'indexes': [], 'children': []},
     {'id': 20,
      'name': 'skipWhitespace:if_1 = 1#[1, -1]',
      'indexes': [],
      'children': []}]}]},
 21: {'id': 21, 'name': 'peek', 'indexes': [], 'children': []},
 22: {'id': 22,
  'name': 'parseNegative:if_1 = 1#[-1]',
  'indexes': [],
  'children': [{'id': 23,
    'name': 'parseValue',
    'indexes': [],
    'children': [{'id': 24,
      'name': 'skipWhitespace',
      'indexes': [],
      'children': [{'id': 25,
        'name': 'hasNext',
        'indexes': [],
        'children': []},
       {'id': 26,
        'name': 'skipWhitespace:while_1 ? [1]',
        'indexes': [],
        'children': [{'id': 27, 'name': 'peek', 'indexes': [], 'children': []},
         {'id': 28,
          'name': 'skipWhitespace:if_1 = 1#[1, -1]',
          'indexes': [],
          'children': []}]}]},
     {'id': 29, 'name': 'peek', 'indexes': [], 'children': []},
     {'id': 30,
      'name': 'parseValue:if_1 = 0#[-1]',
      'indexes': [],
      'children': [{'id': 31,
        'name': 'parseNumber',
        'indexes': [],
        'children': [{'id': 32,
          'name': 'skipWhitespace',
          'indexes': [],
          'children': [{'id': 33,
            'name': 'hasNext',
            'indexes': [],
            'children': []},
           {'id': 34,
            'name': 'skipWhitespace:while_1 ? [1]',
            'indexes': [],
            'children': [{'id': 35,
              'name': 'peek',
              'indexes': [],
              'children': []},
             {'id': 36,
              'name': 'skipWhitespace:if_1 = 1#[1, -1]',
              'indexes': [],
              'children': []}]}]},
         {'id': 37, 'name': 'hasNext', 'indexes': [], 'children': []},
         {'id': 38,
          'name': 'parseNumber:while_1 ? [1]',
          'indexes': [0],
          'children': [{'id': 39,
            'name': 'peek',
            'indexes': [],
            'children': []},
           {'id': 40,
            'name': 'parseNumber:if_1 = 1#[1, -1]',
            'indexes': [],
            'children': []}]},
         {'id': 41, 'name': 'hasNext', 'indexes': [], 'children': []},
         {'id': 42,
          'name': 'parseNumber:while_1 ? [2]',
          'indexes': [1],
          'children': [{'id': 43,
            'name': 'peek',
            'indexes': [],
            'children': []},
           {'id': 44,
            'name': 'parseNumber:if_1 = 1#[2, -1]',
            'indexes': [],
            'children': []}]},
         {'id': 45, 'name': 'hasNext', 'indexes': [], 'children': []},
         {'id': 46,
          'name': 'parseNumber:while_1 ? [3]',
          'indexes': [2],
          'children': [{'id': 47,
            'name': 'peek',
            'indexes': [],
            'children': []},
           {'id': 48,
            'name': 'parseNumber:if_1 = 1#[3, -1]',
            'indexes': [],
            'children': []}]},
         {'id': 49, 'name': 'hasNext', 'indexes': [], 'children': []}]}]}]}]},
 17: {'id': 17, 'name': 'hasNext', 'indexes': [], 'children': []},
 18: {'id': 18,
  'name': 'skipWhitespace:while_1 ? [1]',
  'indexes': [],
  'children': [{'id': 19, 'name': 'peek', 'indexes': [], 'children': []},
   {'id': 20,
    'name': 'skipWhitespace:if_1 = 1#[1, -1]',
    'indexes': [],
    'children': []}]},
 19: {'id': 19, 'name': 'peek', 'indexes': [], 'children': []},
 20: {'id': 20,
  'name': 'skipWhitespace:if_1 = 1#[1, -1]',
  'indexes': [],
  'children': []},
 23: {'id': 23,
  'name': 'parseValue',
  'indexes': [],
  'children': [{'id': 24,
    'name': 'skipWhitespace',
    'indexes': [],
    'children': [{'id': 25, 'name': 'hasNext', 'indexes': [], 'children': []},
     {'id': 26,
      'name': 'skipWhitespace:while_1 ? [1]',
      'indexes': [],
      'children': [{'id': 27, 'name': 'peek', 'indexes': [], 'children': []},
       {'id': 28,
        'name': 'skipWhitespace:if_1 = 1#[1, -1]',
        'indexes': [],
        'children': []}]}]},
   {'id': 29, 'name': 'peek', 'indexes': [], 'children': []},
   {'id': 30,
    'name': 'parseValue:if_1 = 0#[-1]',
    'indexes': [],
    'children': [{'id': 31,
      'name': 'parseNumber',
      'indexes': [],
      'children': [{'id': 32,
        'name': 'skipWhitespace',
        'indexes': [],
        'children': [{'id': 33,
          'name': 'hasNext',
          'indexes': [],
          'children': []},
         {'id': 34,
          'name': 'skipWhitespace:while_1 ? [1]',
          'indexes': [],
          'children': [{'id': 35,
            'name': 'peek',
            'indexes': [],
            'children': []},
           {'id': 36,
            'name': 'skipWhitespace:if_1 = 1#[1, -1]',
            'indexes': [],
            'children': []}]}]},
       {'id': 37, 'name': 'hasNext', 'indexes': [], 'children': []},
       {'id': 38,
        'name': 'parseNumber:while_1 ? [1]',
        'indexes': [0],
        'children': [{'id': 39, 'name': 'peek', 'indexes': [], 'children': []},
         {'id': 40,
          'name': 'parseNumber:if_1 = 1#[1, -1]',
          'indexes': [],
          'children': []}]},
       {'id': 41, 'name': 'hasNext', 'indexes': [], 'children': []},
       {'id': 42,
        'name': 'parseNumber:while_1 ? [2]',
        'indexes': [1],
        'children': [{'id': 43, 'name': 'peek', 'indexes': [], 'children': []},
         {'id': 44,
          'name': 'parseNumber:if_1 = 1#[2, -1]',
          'indexes': [],
          'children': []}]},
       {'id': 45, 'name': 'hasNext', 'indexes': [], 'children': []},
       {'id': 46,
        'name': 'parseNumber:while_1 ? [3]',
        'indexes': [2],
        'children': [{'id': 47, 'name': 'peek', 'indexes': [], 'children': []},
         {'id': 48,
          'name': 'parseNumber:if_1 = 1#[3, -1]',
          'indexes': [],
          'children': []}]},
       {'id': 49, 'name': 'hasNext', 'indexes': [], 'children': []}]}]}]},
 24: {'id': 24,
  'name': 'skipWhitespace',
  'indexes': [],
  'children': [{'id': 25, 'name': 'hasNext', 'indexes': [], 'children': []},
   {'id': 26,
    'name': 'skipWhitespace:while_1 ? [1]',
    'indexes': [],
    'children': [{'id': 27, 'name': 'peek', 'indexes': [], 'children': []},
     {'id': 28,
      'name': 'skipWhitespace:if_1 = 1#[1, -1]',
      'indexes': [],
      'children': []}]}]},
 29: {'id': 29, 'name': 'peek', 'indexes': [], 'children': []},
 30: {'id': 30,
  'name': 'parseValue:if_1 = 0#[-1]',
  'indexes': [],
  'children': [{'id': 31,
    'name': 'parseNumber',
    'indexes': [],
    'children': [{'id': 32,
      'name': 'skipWhitespace',
      'indexes': [],
      'children': [{'id': 33,
        'name': 'hasNext',
        'indexes': [],
        'children': []},
       {'id': 34,
        'name': 'skipWhitespace:while_1 ? [1]',
        'indexes': [],
        'children': [{'id': 35, 'name': 'peek', 'indexes': [], 'children': []},
         {'id': 36,
          'name': 'skipWhitespace:if_1 = 1#[1, -1]',
          'indexes': [],
          'children': []}]}]},
     {'id': 37, 'name': 'hasNext', 'indexes': [], 'children': []},
     {'id': 38,
      'name': 'parseNumber:while_1 ? [1]',
      'indexes': [0],
      'children': [{'id': 39, 'name': 'peek', 'indexes': [], 'children': []},
       {'id': 40,
        'name': 'parseNumber:if_1 = 1#[1, -1]',
        'indexes': [],
        'children': []}]},
     {'id': 41, 'name': 'hasNext', 'indexes': [], 'children': []},
     {'id': 42,
      'name': 'parseNumber:while_1 ? [2]',
      'indexes': [1],
      'children': [{'id': 43, 'name': 'peek', 'indexes': [], 'children': []},
       {'id': 44,
        'name': 'parseNumber:if_1 = 1#[2, -1]',
        'indexes': [],
        'children': []}]},
     {'id': 45, 'name': 'hasNext', 'indexes': [], 'children': []},
     {'id': 46,
      'name': 'parseNumber:while_1 ? [3]',
      'indexes': [2],
      'children': [{'id': 47, 'name': 'peek', 'indexes': [], 'children': []},
       {'id': 48,
        'name': 'parseNumber:if_1 = 1#[3, -1]',
        'indexes': [],
        'children': []}]},
     {'id': 49, 'name': 'hasNext', 'indexes': [], 'children': []}]}]},
 25: {'id': 25, 'name': 'hasNext', 'indexes': [], 'children': []},
 26: {'id': 26,
  'name': 'skipWhitespace:while_1 ? [1]',
  'indexes': [],
  'children': [{'id': 27, 'name': 'peek', 'indexes': [], 'children': []},
   {'id': 28,
    'name': 'skipWhitespace:if_1 = 1#[1, -1]',
    'indexes': [],
    'children': []}]},
 27: {'id': 27, 'name': 'peek', 'indexes': [], 'children': []},
 28: {'id': 28,
  'name': 'skipWhitespace:if_1 = 1#[1, -1]',
  'indexes': [],
  'children': []},
 31: {'id': 31,
  'name': 'parseNumber',
  'indexes': [],
  'children': [{'id': 32,
    'name': 'skipWhitespace',
    'indexes': [],
    'children': [{'id': 33, 'name': 'hasNext', 'indexes': [], 'children': []},
     {'id': 34,
      'name': 'skipWhitespace:while_1 ? [1]',
      'indexes': [],
      'children': [{'id': 35, 'name': 'peek', 'indexes': [], 'children': []},
       {'id': 36,
        'name': 'skipWhitespace:if_1 = 1#[1, -1]',
        'indexes': [],
        'children': []}]}]},
   {'id': 37, 'name': 'hasNext', 'indexes': [], 'children': []},
   {'id': 38,
    'name': 'parseNumber:while_1 ? [1]',
    'indexes': [0],
    'children': [{'id': 39, 'name': 'peek', 'indexes': [], 'children': []},
     {'id': 40,
      'name': 'parseNumber:if_1 = 1#[1, -1]',
      'indexes': [],
      'children': []}]},
   {'id': 41, 'name': 'hasNext', 'indexes': [], 'children': []},
   {'id': 42,
    'name': 'parseNumber:while_1 ? [2]',
    'indexes': [1],
    'children': [{'id': 43, 'name': 'peek', 'indexes': [], 'children': []},
     {'id': 44,
      'name': 'parseNumber:if_1 = 1#[2, -1]',
      'indexes': [],
      'children': []}]},
   {'id': 45, 'name': 'hasNext', 'indexes': [], 'children': []},
   {'id': 46,
    'name': 'parseNumber:while_1 ? [3]',
    'indexes': [2],
    'children': [{'id': 47, 'name': 'peek', 'indexes': [], 'children': []},
     {'id': 48,
      'name': 'parseNumber:if_1 = 1#[3, -1]',
      'indexes': [],
      'children': []}]},
   {'id': 49, 'name': 'hasNext', 'indexes': [], 'children': []}]},
 32: {'id': 32,
  'name': 'skipWhitespace',
  'indexes': [],
  'children': [{'id': 33, 'name': 'hasNext', 'indexes': [], 'children': []},
   {'id': 34,
    'name': 'skipWhitespace:while_1 ? [1]',
    'indexes': [],
    'children': [{'id': 35, 'name': 'peek', 'indexes': [], 'children': []},
     {'id': 36,
      'name': 'skipWhitespace:if_1 = 1#[1, -1]',
      'indexes': [],
      'children': []}]}]},
 37: {'id': 37, 'name': 'hasNext', 'indexes': [], 'children': []},
 38: {'id': 38,
  'name': 'parseNumber:while_1 ? [1]',
  'indexes': [0],
  'children': [{'id': 39, 'name': 'peek', 'indexes': [], 'children': []},
   {'id': 40,
    'name': 'parseNumber:if_1 = 1#[1, -1]',
    'indexes': [],
    'children': []}]},
 41: {'id': 41, 'name': 'hasNext', 'indexes': [], 'children': []},
 42: {'id': 42,
  'name': 'parseNumber:while_1 ? [2]',
  'indexes': [1],
  'children': [{'id': 43, 'name': 'peek', 'indexes': [], 'children': []},
   {'id': 44,
    'name': 'parseNumber:if_1 = 1#[2, -1]',
    'indexes': [],
    'children': []}]},
 45: {'id': 45, 'name': 'hasNext', 'indexes': [], 'children': []},
 46: {'id': 46,
  'name': 'parseNumber:while_1 ? [3]',
  'indexes': [2],
  'children': [{'id': 47, 'name': 'peek', 'indexes': [], 'children': []},
   {'id': 48,
    'name': 'parseNumber:if_1 = 1#[3, -1]',
    'indexes': [],
    'children': []}]},
 49: {'id': 49, 'name': 'hasNext', 'indexes': [], 'children': []},
 33: {'id': 33, 'name': 'hasNext', 'indexes': [], 'children': []},
 34: {'id': 34,
  'name': 'skipWhitespace:while_1 ? [1]',
  'indexes': [],
  'children': [{'id': 35, 'name': 'peek', 'indexes': [], 'children': []},
   {'id': 36,
    'name': 'skipWhitespace:if_1 = 1#[1, -1]',
    'indexes': [],
    'children': []}]},
 35: {'id': 35, 'name': 'peek', 'indexes': [], 'children': []},
 36: {'id': 36,
  'name': 'skipWhitespace:if_1 = 1#[1, -1]',
  'indexes': [],
  'children': []},
 39: {'id': 39, 'name': 'peek', 'indexes': [], 'children': []},
 40: {'id': 40,
  'name': 'parseNumber:if_1 = 1#[1, -1]',
  'indexes': [],
  'children': []},
 43: {'id': 43, 'name': 'peek', 'indexes': [], 'children': []},
 44: {'id': 44,
  'name': 'parseNumber:if_1 = 1#[2, -1]',
  'indexes': [],
  'children': []},
 47: {'id': 47, 'name': 'peek', 'indexes': [], 'children': []},
 48: {'id': 48,
  'name': 'parseNumber:if_1 = 1#[3, -1]',
  'indexes': [],
  'children': []},
 51: {'id': 51,
  'name': 'skipWhitespace',
  'indexes': [],
  'children': [{'id': 52, 'name': 'hasNext', 'indexes': [], 'children': []}]},
 53: {'id': 53, 'name': 'peek', 'indexes': [], 'children': []},
 54: {'id': 54,
  'name': 'parseMultiplication:if_1 = 2#[1, -1]',
  'indexes': [],
  'children': []},
 52: {'id': 52, 'name': 'hasNext', 'indexes': [], 'children': []},
 56: {'id': 56,
  'name': 'skipWhitespace',
  'indexes': [],
  'children': [{'id': 57, 'name': 'hasNext', 'indexes': [], 'children': []}]},
 58: {'id': 58, 'name': 'peek', 'indexes': [], 'children': []},
 59: {'id': 59,
  'name': 'parseAddition:if_1 = 2#[1, -1]',
  'indexes': [],
  'children': []},
 57: {'id': 57, 'name': 'hasNext', 'indexes': [], 'children': []},
 61: {'id': 61, 'name': 'hasNext', 'indexes': [], 'children': []}}
In [95]:
In [96]:
In [97]:
Out[97]:
In [98]:
In [99]:
Out[99]:

We define to_node() a convenience function that, given a list of contiguous indexes and original string, translates it to a leaf node of a tree (that corresponds to the derivation tree syntax in the Fuzzingbook) with a string, empty children, and starting node and ending node.

Convert a list of indexes to a corresponding terminal tree node

In [100]:

Here is how one would use it.

In [101]:
Out[101]:
('9', [], 0, 0)
In [102]:

We now need to identify the terminal (leaf) nodes. For that, we want to group contiguous letters in a node together, and call it a leaf node. So, convert our list of indexes to lists of contiguous indexes first, then convert them to terminal tree nodes. Then, return a set of one level child nodes with contiguous chars from indexes.

In [103]:
In [104]:
Out[104]:
[('9', [], 0, 0)]

Finally, we need to remove the overlap from the trees we have so far. The idea is that, given a node, each child node of that node should be uniquely responsible for a specified range of characters, with no overlap allowed between the children. The starting of the first child to ending of the last child will be the range of the node.

1.6.1.3  Removing Overlap

If overlap is found, the tie is biased to the later child. That is, the later child gets to keep the range, and the former child is recursively traversed to remove overlaps from its children. If a child is completely included in the overlap, the child is excised. A few convenience functions first:

In [105]:
In [106]:
In [107]:
In [108]:
In [109]:

Verify that there is no overlap.

In [110]:

1.6.1.4  Generate derivation tree

Convert a mapped tree to the fuzzingbook style derivation tree.

In [111]:
In [112]:
Out[112]:
In [113]:
Out[113]:

1.6.2  The Complete Miner

We now put everything together. The miner() takes the traces, produces trees out of them, and verifies that the trees actually correspond to the input.

In [114]:
In [115]:

Using the miner()

In [116]:
Out[116]:
In [117]:
Out[117]:

1.7  Generalize Iterations

One of the problems that you can notice in the tree generated is that each while iterations get a different identifier. e.g.

                ('<parse_expr:while_1 ? [2]>', [('+', [], 5, 5)], 5, 5),
                ('<parse_expr:while_1 ? [3]>',
                 [('<parse_expr:if_1 + 0#[3, -1]>',
                   [('<parse_num>',
                     [('<is_digit>', [('7', [], 6, 6)], 6, 6),
                      ('<is_digit>', [('2', [], 7, 7)], 7, 7)],
                     6,
                     7)],
                   6,
                   7)],

The separate identifiers are intentional because we do not yet know the actual dependencies between different iterations such as closing quotes, or closing braces or parenthesis. However, this creates a problem when we mine grammar because we need to match up the compatible nodes.

Generalizer does it through actively doing surgery on the tree to see whether a node is replaceable with another.

In [118]:

1.7.1  Checking compatibility of nodes

We first need a few helper functions. The replace_nodes() function try to replace the contents of the first node with the contents of the second (That is, the tree that has these nodes will automatically be modified), collect the produced string from the tree, and reset any changes. The arguments are tuples with the following format: (node, file_name, tree)

In [119]:

Can a given node be replaced with another? The idea is, given two nodes (possibly from two trees), can the first node be replaced by the second, and still result in a valid string?

In [120]:
In [121]:
In [122]:
In [123]:
In [124]:
In [125]:
In [126]:
In [127]:

1.7.1.1  Using it

In [128]:
In [129]:
In [130]:
Out[130]:
['<parse_expr:while_1 ? [1]>',
 [['<parse_expr:if_1 = 0#[1, -1]>',
   [['<parse_num>', [['<is_digit>', [['9', [], 0, 0]], 0, 0]], 0, 0]],
   0,
   0]],
 0,
 0]
In [131]:
Out[131]:
['<parse_expr:while_1 ? [2]>', [['-', [], 1, 1]], 1, 1]
In [132]:
In [133]:

We need to extract meta information from the names, and update it back. TODO: make the meta info JSON.

In [134]:
In [135]:
Out[135]:
[('parse_expr', 'while', 1, 0, '?', [1]),
 ('parse_expr', 'while', 1, 0, '?', [2]),
 ('parse_expr', 'while', 1, 0, '?', [3]),
 ('parse_expr', 'while', 1, 0, '?', [4]),
 ('parse_expr', 'while', 1, 0, '?', [5]),
 ('parse_expr', 'while', 1, 0, '?', [6]),
 ('parse_expr', 'while', 1, 0, '?', [7])]
In [136]:

Verify that parsing and unparsing works.

In [137]:

1.7.2  Propagate rename of the while node up the child nodes.

The update_stack() when given a node, and a new name, recursively updates the method stack in the children.

In [138]:

Update the node name once we have identified that it corresponds to a global name.

In [139]:

Note that the rename happens only within the current method stack. That is, it does not propagate across method calls. Here is how one would use it.

In [140]:
Out[140]:
['<parse_expr:while_1 ? [3]>',
 [['<parse_expr:if_1 = 2#[3, -1]>',
   [['<parse_paren>',
     [['(', [], 2, 2],
      ['<parse_expr>',
       [['<parse_expr:while_1 ? [1]>',
         [['<parse_expr:if_1 = 0#[1, -1]>',
           [['<parse_num>',
             [['<is_digit>', [['1', [], 3, 3]], 3, 3],
              ['<is_digit>', [['6', [], 4, 4]], 4, 4]],
             3,
             4]],
           3,
           4]],
         3,
         4],
        ['<parse_expr:while_1 ? [2]>', [['+', [], 5, 5]], 5, 5],
        ['<parse_expr:while_1 ? [3]>',
         [['<parse_expr:if_1 = 0#[3, -1]>',
           [['<parse_num>',
             [['<is_digit>', [['7', [], 6, 6]], 6, 6],
              ['<is_digit>', [['2', [], 7, 7]], 7, 7]],
             6,
             7]],
           6,
           7]],
         6,
         7]],
       3,
       7],
      [')', [], 8, 8]],
     2,
     8]],
   2,
   8]],
 2,
 8]

We update the iteration number 3 with a global id 4.0

In [141]:
Out[141]:
['<parse_expr:while_1 ? [4.0]>',
 [['<parse_expr:if_1 = 2#[4.0, -1]>',
   [['<parse_paren>',
     [['(', [], 2, 2],
      ['<parse_expr>',
       [['<parse_expr:while_1 ? [1]>',
         [['<parse_expr:if_1 = 0#[1, -1]>',
           [['<parse_num>',
             [['<is_digit>', [['1', [], 3, 3]], 3, 3],
              ['<is_digit>', [['6', [], 4, 4]], 4, 4]],
             3,
             4]],
           3,
           4]],
         3,
         4],
        ['<parse_expr:while_1 ? [2]>', [['+', [], 5, 5]], 5, 5],
        ['<parse_expr:while_1 ? [3]>',
         [['<parse_expr:if_1 = 0#[3, -1]>',
           [['<parse_num>',
             [['<is_digit>', [['7', [], 6, 6]], 6, 6],
              ['<is_digit>', [['2', [], 7, 7]], 7, 7]],
             6,
             7]],
           6,
           7]],
         6,
         7]],
       3,
       7],
      [')', [], 8, 8]],
     2,
     8]],
   2,
   8]],
 2,
 8]
replace a set of nodes

We want to replace the while loop iteration identifiers with a global identifier. For that, we are given a list of nodes that are compatible with global ones. We first extract the iteration id from the global node, and apply it on the while node under consideration.

In [142]:

1.7.3  Generalize a given set of loops

The main workhorse. It generalizes the looping constructs. It is given a set of while loops with the same label under the current node. TODO: Refactor when we actually have time.

Helper: node inclusion

Checking for node inclusion. We do not want to try including a first node in second if the first node already contains the second. It will lead to infinite loop on tree_to_string().

In [143]:
Helper: sorting

Ordering nodes by their highest complexity to avoid spurious can-replace answers.

In [144]:
In [145]:

First, we check whether any of the loops we have are compatible with the globally registered loops in while_register.

In [146]:

Next, for all the loops that remain, check if they can be deleted. If they can be, we want to place Epsilon == * in place of ? in the can_empty position.

In [147]:

Next, we check all current loops whether they are compatible with each other. Essentially, we start from the back, and check if the first or second or third ... nodes are compatible with the last node. Then take the second last node and do the same.

If they are, we use the same name for all compatible nodes.

In [148]:

Finally, register all the new while loops discovered.

In [149]:

All together.

In [150]:

We keep a global registry of nodes, so that we can use the same iteration labels.

In [151]:

1.7.4  Collect loops to generalize

The idea is to look through the tree, looking for while loops. When one sees a while loop, start at one end, and see if the while iteration index can be replaced by the first one, and vice versa. If not, try with the second one and so on until the first one succeeds. When one succeeds, replace the definition of the matching one with an alternate with the last's definition, and replace the name of last with the first, and delete last. Here, we only collect the while loops with same labels, with generalize_loop() doing the rest.

In [152]:

We need the ability for fairly deep surgery. So we dump and load the mined trees to convert tuples to arrays.

In [153]:
In [154]:
In [155]:
Out[155]:
In [156]:
Out[156]:

1.8  Generating a Grammar

Generating a grammar from the generalized derivation trees is pretty simple. Start at the start node, and any node that represents a method or a pseudo method becomes a nonterminal. The children forms alternate expansions for the nonterminal. Since all the keys are compatible, merging the grammar is simply merging the hash map.

First, we define a pretty printer for grammar.

In [157]:
In [158]:
In [159]:

1.8.1  Trees to grammar

In [160]:
In [161]:
In [162]:
In [163]:
Out[163]:
{'<START>': [('<main>',)],
 '<main>': [('<parse_expr>',)],
 '<parse_expr>': [('<parse_expr:while_1 = [1.0]>',),
  ('<parse_expr:while_1 = [1.0]>',
   '<parse_expr:while_1 - [2.0]>',
   '<parse_expr:while_1 = [1.0]>'),
  ('<parse_expr:while_1 = [1.0]>',
   '<parse_expr:while_1 - [2.0]>',
   '<parse_expr:while_1 = [1.0]>',
   '<parse_expr:while_1 - [2.0]>',
   '<parse_expr:while_1 = [1.0]>'),
  ('<parse_expr:while_1 = [1.0]>',
   '<parse_expr:while_1 - [2.0]>',
   '<parse_expr:while_1 = [1.0]>',
   '<parse_expr:while_1 - [2.0]>',
   '<parse_expr:while_1 = [1.0]>',
   '<parse_expr:while_1 - [2.0]>',
   '<parse_expr:while_1 = [1.0]>')],
 '<parse_expr:while_1 = [1.0]>': [('<parse_expr:if_1 = 0#[1.0, -1]>',),
  ('<parse_expr:if_1 = 2#[1.0, -1]>',)],
 '<parse_expr:while_1 - [2.0]>': [('*',), ('+',), ('-',), ('/',)],
 '<parse_expr:if_1 = 0#[1.0, -1]>': [('<parse_num>',)],
 '<parse_expr:if_1 = 2#[1.0, -1]>': [('<parse_paren>',)],
 '<parse_num>': [('<is_digit>',),
  ('<is_digit>', '<is_digit>'),
  ('<is_digit>', '<is_digit>', '<is_digit>')],
 '<is_digit>': [('0',),
  ('1',),
  ('2',),
  ('3',),
  ('4',),
  ('5',),
  ('6',),
  ('7',),
  ('8',),
  ('9',)],
 '<parse_paren>': [('(', '<parse_expr>', ')')]}
In [164]:
Out[164]:
{'<START>': [('<main>',)],
 '<main>': [('<getValue>',)],
 '<getValue>': [('<parseExpression>',)],
 '<parseExpression>': [('<parseAddition>',)],
 '<parseAddition>': [('<parseMultiplication>',),
  ('<parseMultiplication>', '<parseAddition:while_1 - [1.0]>')],
 '<parseMultiplication>': [('<parseParenthesis>',),
  ('<parseParenthesis>', '<parseMultiplication:while_1 - [1.0]>')],
 '<parseAddition:while_1 - [1.0]>': [('+',
   '<parseAddition:if_1 = 0#[1.0, -1]>')],
 '<parseParenthesis>': [('<parseParenthesis:if_1 = 1#[-1]>',),
  ('<skipWhitespace>', '<parseParenthesis:if_1 = 1#[-1]>')],
 '<parseMultiplication:while_1 - [1.0]>': [('<skipWhitespace>',),
  ('<skipWhitespace>', '*', '<parseMultiplication:if_1 = 0#[1.0, -1]>')],
 '<parseParenthesis:if_1 = 1#[-1]>': [('<parseNegative>',)],
 '<skipWhitespace>': [('<skipWhitespace:while_1 - [1.0]>',)],
 '<parseNegative>': [('<parseNegative:if_1 = 1#[-1]>',)],
 '<parseNegative:if_1 = 1#[-1]>': [('<parseValue>',)],
 '<parseValue>': [('<parseValue:if_1 = 0#[-1]>',)],
 '<parseValue:if_1 = 0#[-1]>': [('<parseNumber>',)],
 '<parseNumber>': [('<parseNumber:while_1 - [1.0]>',),
  ('<parseNumber:while_1 - [1.0]>',
   '<parseNumber:while_1 - [1.0]>',
   '<parseNumber:while_1 - [1.0]>')],
 '<parseNumber:while_1 - [1.0]>': [('0',),
  ('1',),
  ('2',),
  ('3',),
  ('4',),
  ('5',)],
 '<skipWhitespace:while_1 - [1.0]>': [(' ',)],
 '<parseMultiplication:if_1 = 0#[1.0, -1]>': [('<parseParenthesis>',)],
 '<parseAddition:if_1 = 0#[1.0, -1]>': [('<parseMultiplication>',)]}

The grammar generated may still contain meta characters such as < and >. We need to cleanup these to make it a grammar that is fuzzable using the Fuzzingbook fuzzers.

In [165]:
In [166]:
In [167]:
(6+9-8+0)-((4)-(5))/(4+0)
5/011
204/(9/4/5*0)
10+(((2/4-8))/584*41)/((((3*9*8)*07)))
(2/(0))/(8-4+2)*(4)*(9/0)
434/48/9-585
546-6
3/315*((2)*(3)-5)/(2/6+1/0)
(((1/0)*27-(3/8-9+5)))/(6)
0*9*(1+2-7-0)
In [168]:
2 *145
1 * 2+ 401
 5 
254 
 301+032
 004 +5
4 * 2+011
1+420 
224
 2

1.8.2  Inserting Empty Alternatives for IF and Loops

Next, we want to insert empty rules for those loops and conditionals that can be skipped. For loops, the entire sequence has to contain the empty marker.

In [169]:
In [170]:
Out[170]:
{'<START>': [('<main>',)],
 '<main>': [('<parse_expr>',)],
 '<parse_expr>': [('<parse_expr:while_1 = [1.0]>',),
  ('<parse_expr:while_1 = [1.0]>',
   '<parse_expr:while_1 - [2.0]>',
   '<parse_expr:while_1 = [1.0]>'),
  ('<parse_expr:while_1 = [1.0]>',
   '<parse_expr:while_1 - [2.0]>',
   '<parse_expr:while_1 = [1.0]>',
   '<parse_expr:while_1 - [2.0]>',
   '<parse_expr:while_1 = [1.0]>'),
  ('<parse_expr:while_1 = [1.0]>',
   '<parse_expr:while_1 - [2.0]>',
   '<parse_expr:while_1 = [1.0]>',
   '<parse_expr:while_1 - [2.0]>',
   '<parse_expr:while_1 = [1.0]>',
   '<parse_expr:while_1 - [2.0]>',
   '<parse_expr:while_1 = [1.0]>')],
 '<parse_expr:while_1 = [1.0]>': [('<parse_expr:if_1 = 0#[1.0, -1]>',),
  ('<parse_expr:if_1 = 2#[1.0, -1]>',)],
 '<parse_expr:while_1 - [2.0]>': [('*',), ('+',), ('-',), ('/',)],
 '<parse_expr:if_1 = 0#[1.0, -1]>': [('<parse_num>',)],
 '<parse_expr:if_1 = 2#[1.0, -1]>': [('<parse_paren>',)],
 '<parse_num>': [('<is_digit>',),
  ('<is_digit>', '<is_digit>'),
  ('<is_digit>', '<is_digit>', '<is_digit>')],
 '<is_digit>': [('0',),
  ('1',),
  ('2',),
  ('3',),
  ('4',),
  ('5',),
  ('6',),
  ('7',),
  ('8',),
  ('9',)],
 '<parse_paren>': [('(', '<parse_expr>', ')')]}
In [171]:
'20'
'(0*7*2+5)*(2/1)'
'((56+1+53)*((905)))'
'59'
'(7*(((((8)/((1+3+3)+(6-3*1))))*9*710)))'
'28/3*75*40'
'0/((2)/(8+4)/11)/((95/((4*3+6*9))))+6'
'96-9'
'(649-(5/1+((((212-76))/608)/4)*66))-18'
'((2))'
In [172]:
Out[172]:
{'<START>': [('<main>',)],
 '<main>': [('<getValue>',)],
 '<getValue>': [('<parseExpression>',)],
 '<parseExpression>': [('<parseAddition>',)],
 '<parseAddition>': [('<parseMultiplication>',),
  ('<parseMultiplication>', '<parseAddition:while_1 - [1.0]>')],
 '<parseMultiplication>': [('<parseParenthesis>',),
  ('<parseParenthesis>', '<parseMultiplication:while_1 - [1.0]>')],
 '<parseAddition:while_1 - [1.0]>': [('+',
   '<parseAddition:if_1 = 0#[1.0, -1]>')],
 '<parseParenthesis>': [('<parseParenthesis:if_1 = 1#[-1]>',),
  ('<skipWhitespace>', '<parseParenthesis:if_1 = 1#[-1]>')],
 '<parseMultiplication:while_1 - [1.0]>': [('<skipWhitespace>',),
  ('<skipWhitespace>', '*', '<parseMultiplication:if_1 = 0#[1.0, -1]>')],
 '<parseParenthesis:if_1 = 1#[-1]>': [('<parseNegative>',)],
 '<skipWhitespace>': [('<skipWhitespace:while_1 - [1.0]>',)],
 '<parseNegative>': [('<parseNegative:if_1 = 1#[-1]>',)],
 '<parseNegative:if_1 = 1#[-1]>': [('<parseValue>',)],
 '<parseValue>': [('<parseValue:if_1 = 0#[-1]>',)],
 '<parseValue:if_1 = 0#[-1]>': [('<parseNumber>',)],
 '<parseNumber>': [('<parseNumber:while_1 - [1.0]>',),
  ('<parseNumber:while_1 - [1.0]>',
   '<parseNumber:while_1 - [1.0]>',
   '<parseNumber:while_1 - [1.0]>')],
 '<parseNumber:while_1 - [1.0]>': [('0',),
  ('1',),
  ('2',),
  ('3',),
  ('4',),
  ('5',)],
 '<skipWhitespace:while_1 - [1.0]>': [(' ',)],
 '<parseMultiplication:if_1 = 0#[1.0, -1]>': [('<parseParenthesis>',)],
 '<parseAddition:if_1 = 0#[1.0, -1]>': [('<parseMultiplication>',)]}
In [173]:
'4 * 1'
' 4+ 1'
' 051 *155+ 3'
' 303 +512 '
'2+ 2 * 1'
'124 + 5'
'444+ 221'
'4+5 '
'3 *1'
'0+233'

1.8.3  Learning Regular Expressions

We now need to generalize the loops. The idea is to look for patterns exclusively in the similarly named while loops using any of the regular expression learners. For the prototype, we replaced the modified Sequitur with the modified Fernau which gave us better regular expressions than before. The main constraint we have is that we want to avoid repeated execution of program if possible. Fernau algorithm can recover a reasonably approximate regular exression based only on positive data.

1.8.3.1  The modified Fernau algorithm

The Fernau algorithm is from Algorithms for learning regular expressions from positive data by HenningFernau. Our algorithm uses a modified form of the Prefix-Tree-Acceptor from Fernau. First we define an LRF buffer of a given size.

In [174]:

The add1() takes in an array, and transfers the first element of the array into the end of current buffer, and simultaneously drops the first element of the buffer.

In [175]:

For equality between the buffer and an array, we only compare when both the array and the items are actually elements and not chunked arrays.

In [176]:

The detect_chunks() detects any repeating portions of a list of n size.

In [177]:

Once we have detected plausible repeating sequences, we gather all similar sequences into arrays.

In [178]:

The identify_chunks() simply calls the detect_chunks() on all given lists, and then converts all chunks identified into arrays.

In [179]:
Prefix tree acceptor

The prefix tree acceptor is a way to represent positive data. The Node class holds a single node in the prefix tree acceptor.

In [180]:
In [181]:

Given a rule, determine the abstraction for it.

In [182]:
In [183]:
In [184]:
Out[184]:
{'<START>': [['<START-1>']],
 '<START-1>': [['<main>']],
 '<main>': [['<main-1>']],
 '<main-1>': [['<parse_expr>']],
 '<parse_expr>': [['<parse_expr-0-c>']],
 '<parse_expr-0-c>': [['<parse_expr-1>'], ['<parse_expr-3>']],
 '<parse_expr-1>': [['<parse_expr-1-s>', '<parse_expr-2>']],
 '<parse_expr-3>': [['<parse_expr:while_1 = [1.0]>']],
 '<parse_expr-1-s>': [['<parse_expr:while_1 = [1.0]>',
   '<parse_expr:while_1 - [2.0]>'],
  ['<parse_expr:while_1 = [1.0]>',
   '<parse_expr:while_1 - [2.0]>',
   '<parse_expr-1-s>']],
 '<parse_expr-2>': [['<parse_expr:while_1 = [1.0]>']],
 '<parse_expr:while_1 = [1.0]>': [['<parse_expr:while_1 = [1.0]-0-c>']],
 '<parse_expr:while_1 - [2.0]>': [['<parse_expr:while_1 - [2.0]-0-c>']],
 '<parse_expr:while_1 = [1.0]-0-c>': [['<parse_expr:while_1 = [1.0]-1>'],
  ['<parse_expr:while_1 = [1.0]-2>']],
 '<parse_expr:while_1 = [1.0]-1>': [['<parse_expr:if_1 = 2#[1.0, -1]>']],
 '<parse_expr:while_1 = [1.0]-2>': [['<parse_expr:if_1 = 0#[1.0, -1]>']],
 '<parse_expr:if_1 = 2#[1.0, -1]>': [['<parse_expr:if_1 = 2#[1.0, -1]-1>']],
 '<parse_expr:if_1 = 2#[1.0, -1]-1>': [['<parse_paren>']],
 '<parse_paren>': [['<parse_paren-1>']],
 '<parse_paren-1>': [['(', '<parse_paren-2>']],
 '<parse_paren-2>': [['<parse_expr>', '<parse_paren-3>']],
 '<parse_paren-3>': [[')']],
 '<parse_expr:if_1 = 0#[1.0, -1]>': [['<parse_expr:if_1 = 0#[1.0, -1]-1>']],
 '<parse_expr:if_1 = 0#[1.0, -1]-1>': [['<parse_num>']],
 '<parse_num>': [['<parse_num-1>']],
 '<parse_num-1>': [['<parse_num-1-s>']],
 '<parse_num-1-s>': [['<is_digit>'], ['<is_digit>', '<parse_num-1-s>']],
 '<is_digit>': [['<is_digit-0-c>']],
 '<is_digit-0-c>': [['<is_digit-10>'],
  ['<is_digit-1>'],
  ['<is_digit-2>'],
  ['<is_digit-3>'],
  ['<is_digit-4>'],
  ['<is_digit-5>'],
  ['<is_digit-6>'],
  ['<is_digit-7>'],
  ['<is_digit-8>'],
  ['<is_digit-9>']],
 '<is_digit-10>': [['4']],
 '<is_digit-1>': [['1']],
 '<is_digit-2>': [['6']],
 '<is_digit-3>': [['9']],
 '<is_digit-4>': [['2']],
 '<is_digit-5>': [['3']],
 '<is_digit-6>': [['8']],
 '<is_digit-7>': [['0']],
 '<is_digit-8>': [['5']],
 '<is_digit-9>': [['7']],
 '<parse_expr:while_1 - [2.0]-0-c>': [['<parse_expr:while_1 - [2.0]-1>'],
  ['<parse_expr:while_1 - [2.0]-2>'],
  ['<parse_expr:while_1 - [2.0]-3>'],
  ['<parse_expr:while_1 - [2.0]-4>']],
 '<parse_expr:while_1 - [2.0]-1>': [['/']],
 '<parse_expr:while_1 - [2.0]-2>': [['-']],
 '<parse_expr:while_1 - [2.0]-3>': [['*']],
 '<parse_expr:while_1 - [2.0]-4>': [['+']]}
In [185]:
152 
 510+0 * 0
 402 *442
 311
 134+ 3
 1+3
003 
405+1 
0
 4 * 2+443 *2
In [186]:
Out[186]:
{'<START>': [['<START-1>']],
 '<START-1>': [['<main>']],
 '<main>': [['<main-1>']],
 '<main-1>': [['<getValue>']],
 '<getValue>': [['<getValue-1>']],
 '<getValue-1>': [['<parseExpression>']],
 '<parseExpression>': [['<parseExpression-1>']],
 '<parseExpression-1>': [['<parseAddition>']],
 '<parseAddition>': [['<parseAddition-1>']],
 '<parseAddition-1>': [['<parseMultiplication>'],
  ['<parseMultiplication>', '<parseAddition-2>']],
 '<parseMultiplication>': [['<parseMultiplication-1>']],
 '<parseAddition-2>': [['<parseAddition:while_1 - [1.0]>']],
 '<parseMultiplication-1>': [['<parseParenthesis>'],
  ['<parseParenthesis>', '<parseMultiplication-2>']],
 '<parseParenthesis>': [['<parseParenthesis-0-c>']],
 '<parseMultiplication-2>': [['<parseMultiplication:while_1 - [1.0]>']],
 '<parseParenthesis-0-c>': [['<parseParenthesis-1>'],
  ['<parseParenthesis-3>']],
 '<parseParenthesis-1>': [['<skipWhitespace>', '<parseParenthesis-2>']],
 '<parseParenthesis-3>': [['<parseParenthesis:if_1 = 1#[-1]>']],
 '<skipWhitespace>': [['<skipWhitespace-1>']],
 '<parseParenthesis-2>': [['<parseParenthesis:if_1 = 1#[-1]>']],
 '<skipWhitespace-1>': [['<skipWhitespace:while_1 - [1.0]>']],
 '<skipWhitespace:while_1 - [1.0]>': [['<skipWhitespace:while_1 - [1.0]-1>']],
 '<skipWhitespace:while_1 - [1.0]-1>': [[' ']],
 '<parseParenthesis:if_1 = 1#[-1]>': [['<parseParenthesis:if_1 = 1#[-1]-1>']],
 '<parseParenthesis:if_1 = 1#[-1]-1>': [['<parseNegative>']],
 '<parseNegative>': [['<parseNegative-1>']],
 '<parseNegative-1>': [['<parseNegative:if_1 = 1#[-1]>']],
 '<parseNegative:if_1 = 1#[-1]>': [['<parseNegative:if_1 = 1#[-1]-1>']],
 '<parseNegative:if_1 = 1#[-1]-1>': [['<parseValue>']],
 '<parseValue>': [['<parseValue-1>']],
 '<parseValue-1>': [['<parseValue:if_1 = 0#[-1]>']],
 '<parseValue:if_1 = 0#[-1]>': [['<parseValue:if_1 = 0#[-1]-1>']],
 '<parseValue:if_1 = 0#[-1]-1>': [['<parseNumber>']],
 '<parseNumber>': [['<parseNumber-1>']],
 '<parseNumber-1>': [['<parseNumber-1-s>']],
 '<parseNumber-1-s>': [['<parseNumber:while_1 - [1.0]>'],
  ['<parseNumber:while_1 - [1.0]>', '<parseNumber-1-s>']],
 '<parseNumber:while_1 - [1.0]>': [['<parseNumber:while_1 - [1.0]-0-c>']],
 '<parseNumber:while_1 - [1.0]-0-c>': [['<parseNumber:while_1 - [1.0]-1>'],
  ['<parseNumber:while_1 - [1.0]-2>'],
  ['<parseNumber:while_1 - [1.0]-3>'],
  ['<parseNumber:while_1 - [1.0]-4>'],
  ['<parseNumber:while_1 - [1.0]-5>'],
  ['<parseNumber:while_1 - [1.0]-6>']],
 '<parseNumber:while_1 - [1.0]-1>': [['1']],
 '<parseNumber:while_1 - [1.0]-2>': [['2']],
 '<parseNumber:while_1 - [1.0]-3>': [['0']],
 '<parseNumber:while_1 - [1.0]-4>': [['3']],
 '<parseNumber:while_1 - [1.0]-5>': [['5']],
 '<parseNumber:while_1 - [1.0]-6>': [['4']],
 '<parseMultiplication:while_1 - [1.0]>': [['<parseMultiplication:while_1 - [1.0]-1>']],
 '<parseMultiplication:while_1 - [1.0]-1>': [['<skipWhitespace>'],
  ['<skipWhitespace>', '<parseMultiplication:while_1 - [1.0]-2>']],
 '<parseMultiplication:while_1 - [1.0]-2>': [['*',
   '<parseMultiplication:while_1 - [1.0]-3>']],
 '<parseMultiplication:while_1 - [1.0]-3>': [['<parseMultiplication:if_1 = 0#[1.0, -1]>']],
 '<parseMultiplication:if_1 = 0#[1.0, -1]>': [['<parseMultiplication:if_1 = 0#[1.0, -1]-1>']],
 '<parseMultiplication:if_1 = 0#[1.0, -1]-1>': [['<parseParenthesis>']],
 '<parseAddition:while_1 - [1.0]>': [['<parseAddition:while_1 - [1.0]-1>']],
 '<parseAddition:while_1 - [1.0]-1>': [['+',
   '<parseAddition:while_1 - [1.0]-2>']],
 '<parseAddition:while_1 - [1.0]-2>': [['<parseAddition:if_1 = 0#[1.0, -1]>']],
 '<parseAddition:if_1 = 0#[1.0, -1]>': [['<parseAddition:if_1 = 0#[1.0, -1]-1>']],
 '<parseAddition:if_1 = 0#[1.0, -1]-1>': [['<parseMultiplication>']]}
In [187]:
404
 5052 
 154+ 3
24 *5+5
222 * 224+ 01 
 05+252 
255
2
1+ 0110
 42
In [188]:
00/(((7/99+((6)/(6/(1)))+7)))
(1)+415748/8
8
451
((0273-948))
(7-5*0)*(8+1+6*2)
1
67+(5)*3
((91/4))
(9*1*(53))*(6/1)*182
In [189]:
In [190]:
Out[190]:
{'<START>': ['<START-1>'],
 '<START-1>': ['<main>'],
 '<main>': ['<main-1>'],
 '<main-1>': ['<parse_expr>'],
 '<parse_expr>': ['<parse_expr-0-c>'],
 '<parse_expr-0-c>': ['<parse_expr-1>', '<parse_expr-3>'],
 '<parse_expr-1>': ['<parse_expr-1-s><parse_expr-2>'],
 '<parse_expr-3>': ['<parse_expr:while_1_=_[1.0]>'],
 '<parse_expr-1-s>': ['<parse_expr:while_1_=_[1.0]><parse_expr:while_1_-_[2.0]>',
  '<parse_expr:while_1_=_[1.0]><parse_expr:while_1_-_[2.0]><parse_expr-1-s>'],
 '<parse_expr-2>': ['<parse_expr:while_1_=_[1.0]>'],
 '<parse_expr:while_1_=_[1.0]>': ['<parse_expr:while_1_=_[1.0]-0-c>'],
 '<parse_expr:while_1_-_[2.0]>': ['<parse_expr:while_1_-_[2.0]-0-c>'],
 '<parse_expr:while_1_=_[1.0]-0-c>': ['<parse_expr:while_1_=_[1.0]-1>',
  '<parse_expr:while_1_=_[1.0]-2>'],
 '<parse_expr:while_1_=_[1.0]-1>': ['<parse_expr:if_1_=_2#[1.0,_-1]>'],
 '<parse_expr:while_1_=_[1.0]-2>': ['<parse_expr:if_1_=_0#[1.0,_-1]>'],
 '<parse_expr:if_1_=_2#[1.0,_-1]>': ['<parse_expr:if_1_=_2#[1.0,_-1]-1>'],
 '<parse_expr:if_1_=_2#[1.0,_-1]-1>': ['<parse_paren>'],
 '<parse_paren>': ['<parse_paren-1>'],
 '<parse_paren-1>': ['(<parse_paren-2>'],
 '<parse_paren-2>': ['<parse_expr><parse_paren-3>'],
 '<parse_paren-3>': [')'],
 '<parse_expr:if_1_=_0#[1.0,_-1]>': ['<parse_expr:if_1_=_0#[1.0,_-1]-1>'],
 '<parse_expr:if_1_=_0#[1.0,_-1]-1>': ['<parse_num>'],
 '<parse_num>': ['<parse_num-1>'],
 '<parse_num-1>': ['<parse_num-1-s>'],
 '<parse_num-1-s>': ['<is_digit>', '<is_digit><parse_num-1-s>'],
 '<is_digit>': ['<is_digit-0-c>'],
 '<is_digit-0-c>': ['<is_digit-10>',
  '<is_digit-1>',
  '<is_digit-2>',
  '<is_digit-3>',
  '<is_digit-4>',
  '<is_digit-5>',
  '<is_digit-6>',
  '<is_digit-7>',
  '<is_digit-8>',
  '<is_digit-9>'],
 '<is_digit-10>': ['4'],
 '<is_digit-1>': ['1'],
 '<is_digit-2>': ['6'],
 '<is_digit-3>': ['9'],
 '<is_digit-4>': ['2'],
 '<is_digit-5>': ['3'],
 '<is_digit-6>': ['8'],
 '<is_digit-7>': ['0'],
 '<is_digit-8>': ['5'],
 '<is_digit-9>': ['7'],
 '<parse_expr:while_1_-_[2.0]-0-c>': ['<parse_expr:while_1_-_[2.0]-1>',
  '<parse_expr:while_1_-_[2.0]-2>',
  '<parse_expr:while_1_-_[2.0]-3>',
  '<parse_expr:while_1_-_[2.0]-4>'],
 '<parse_expr:while_1_-_[2.0]-1>': ['/'],
 '<parse_expr:while_1_-_[2.0]-2>': ['-'],
 '<parse_expr:while_1_-_[2.0]-3>': ['*'],
 '<parse_expr:while_1_-_[2.0]-4>': ['+']}
In [191]:
In [192]:
In [193]:
(9+7+1-6*(8/9*1))
(79*489+(643-(89))-(6))
((64))-((0)*1)+0/0-0/1*65
(2/95)
((107038*((((959385427839*(8+(53)))/2)-2/920)))+20266)
152+89
09
(3+(434)-(55-9))
((345)/(((((96*474-(86*(((((5)-66)))*(9+(((20)*(6/(724))+073-((9)))-95)))))))))+36)
(((628)))/((3315+4))+8/(78119)

1.8.4  Remove duplicate and redundant entries

In [194]:

Return a new symbol for grammar based on symbol_name.

In [195]:

Replace keys that have a single token definition with the token in the defition.

In [196]:
In [197]:
In [198]:
In [199]:

Remove keys that have similar rules.

In [200]:
In [201]:

Remove all the control flow vestiges from names, and simply name them sequentially.

In [202]:
In [203]:
In [204]:

Remove keys that are referred to only from a single rule, and which have a single alternative. Import. This can't work on canonical representation. First, given a key, we figure out its distance to <START>.

This is different from remove_single_entries() in that, there we do not care if the key is being used multiple times. Here, we only replace keys that are referred to only once.

In [205]:
In [206]:
In [207]:

Next, we generate a map of child -> [parents].

In [208]:

Now, all together.

In [209]:

1.9  Accio Grammar

In [210]:
In [211]:
In [212]:
In [213]:
Out[213]:
{'<START>': ['<parse_expr-1>'],
 '<parse_expr-1>': ['<parse_expr-3>',
  '<parse_expr-3><parse_expr><parse_expr-3>'],
 '<parse_expr-3>': ['(<parse_expr-1>)', '<is_digit-0-c>'],
 '<parse_expr>': ['+', '-'],
 '<is_digit-0-c>': ['1', '2']}
In [214]:
In [215]:
(2)
2+(2)
((2-((1)))-1)-((2)-(2))
(1)+(((1))-(1+(((2-1))-((1-1)-(((2-(2-1))+2)+(((1-((2-1)))+1)-2))))))
1+1
2
(((1+(((1-1))-(((1+2)+2))))))-1
1
1-1
(2+((1)))

1.10  Libraries

We need a few instrumented supporting libraries.

1.10.1  StringIO replacement

In [216]:
In [217]:

1.10.2  ShLex Replacement

In [218]:
In [219]:

2  Evaluation

In [220]:
In [221]:

2.1  Initialization

In [222]:
In [223]:
In [224]:

2.1.1  Check Recall

How many of the valid inputs from the golden grammar can be recognized by a parser using our grammar?

In [225]:

2.1.2  Check Precision

How many of the inputs produced using our grammar are valid? (Accepted by the program).

In [226]:

2.1.3  Timer

In [227]:
In [228]:
In [229]:
In [230]:
In [231]:
In [232]:
In [233]:
In [234]:
In [235]:
In [236]:

2.2  Subjects

In [237]:

2.2.1  CGIDecode

2.2.1.1  Golden Grammar

In [238]:
In [239]:

2.2.1.2  Samples

In [240]:
In [241]:

2.2.1.3  Mimid

In [242]:
Out[242]:
{'<START>': ['<cgi_decode-1-s>'],
 '<cgi_decode-1-s>': ['<cgi_decode-1>', '<cgi_decode-1><cgi_decode-1-s>'],
 '<cgi_decode-1>': ['%<cgi_decode>',
  '&',
  '+',
  '-',
  '.',
  '/',
  '0',
  '1',
  '2',
  '3',
  '4',
  '5',
  '6',
  '7',
  '8',
  '9',
  ':',
  '=',
  '?',
  'A',
  'B',
  'C',
  'D',
  'E',
  'F',
  'G',
  'H',
  'I',
  'J',
  'K',
  'L',
  'M',
  'N',
  'O',
  'P',
  'Q',
  'R',
  'S',
  'T',
  'U',
  'V',
  'W',
  'X',
  'Y',
  'Z',
  '_',
  'a',
  'b',
  'c',
  'd',
  'e',
  'f',
  'g',
  'h',
  'i',
  'j',
  'k',
  'l',
  'm',
  'n',
  'o',
  'p',
  'q',
  'r',
  's',
  't',
  'u',
  'v',
  'w',
  'x',
  'y',
  'z',
  '~'],
 '<cgi_decode>': ['00',
  '20',
  '21',
  '22',
  '23',
  '24',
  '25',
  '26',
  '27',
  '28',
  '29',
  '2A',
  '2B',
  '2C',
  '2D',
  '2E',
  '2F',
  '2a',
  '2b',
  '2c',
  '2d',
  '2e',
  '2f',
  '3A',
  '3B',
  '3C',
  '3D',
  '3E',
  '3F',
  '3a',
  '3b',
  '3c',
  '3d',
  '3e',
  '3f',
  '40',
  '5B',
  '5C',
  '5D',
  '5E',
  '5F',
  '5b',
  '5c',
  '5d',
  '5e',
  '5f',
  '60',
  '7B',
  '7C',
  '7D',
  '7E',
  '7b',
  '7c',
  '7d',
  '7e']}
In [243]:
(1000, 1000)
In [244]:
In [245]:
(1000, 1000)

2.2.1.4  Autogram

In [246]:
CPU times: user 11.8 ms, sys: 8.75 ms, total: 20.6 ms
Wall time: 24.9 s
In [247]:
Out[247]:
{'<START>': ['<create@27:self>'],
 '<create@27:self>': ['-',
  '1',
  '<__init__@15:self>',
  '<__init__@15:self><cgi_decode@19:c><cgi_decode@19:c><cgi_decode@19:c><cgi_decode@19:c>',
  '<__init__@15:self><cgi_decode@19:c><cgi_decode@19:c><cgi_decode@19:c><cgi_decode@19:c><cgi_decode@19:c><cgi_decode@19:c><cgi_decode@19:c><cgi_decode@19:c>+<cgi_decode@19:c><cgi_decode@19:c>+me<cgi_decode@19:c><cgi_decode@23:digit_high><cgi_decode@23:digit_low><cgi_decode@19:c><cgi_decode@19:c><cgi_decode@19:c>zin<cgi_decode@19:c><cgi_decode@19:c>oo<cgi_decode@19:c><cgi_decode@19:c>o<cgi_decode@19:c>g',
  '<__init__@15:self><cgi_decode@19:c><cgi_decode@19:c><cgi_decode@19:c><cgi_decode@19:c><cgi_decode@19:c><cgi_decode@19:c><cgi_decode@19:c><cgi_decode@19:c><cgi_decode@19:c>',
  '<__init__@15:self><cgi_decode@19:c><cgi_decode@19:c><cgi_decode@19:c><cgi_decode@19:c><cgi_decode@19:c><cgi_decode@19:c><cgi_decode@19:c><cgi_decode@19:c><cgi_decode@19:c><cgi_decode@19:c><cgi_decode@19:c><cgi_decode@19:c><cgi_decode@19:c><cgi_decode@19:c><cgi_decode@19:c><cgi_decode@19:c><cgi_decode@19:c><cgi_decode@19:c><cgi_decode@19:c><cgi_decode@19:c><cgi_decode@19:c><cgi_decode@19:c><cgi_decode@19:c><cgi_decode@19:c><cgi_decode@19:c><cgi_decode@19:c><cgi_decode@19:c><cgi_decode@19:c><cgi_decode@19:c><cgi_decode@19:c><cgi_decode@19:c><cgi_decode@19:c><cgi_decode@19:c><cgi_decode@19:c><cgi_decode@19:c><cgi_decode@19:c><cgi_decode@19:c><cgi_decode@19:c><cgi_decode@19:c><cgi_decode@19:c><cgi_decode@19:c><cgi_decode@19:c><cgi_decode@19:c><cgi_decode@19:c><cgi_decode@19:c><cgi_decode@19:c><cgi_decode@19:c><cgi_decode@19:c><cgi_decode@19:c><cgi_decode@19:c><cgi_decode@19:c>',
  '<__init__@15:self><cgi_decode@19:c><cgi_decode@19:c><cgi_decode@19:c><cgi_decode@19:c><cgi_decode@19:c><cgi_decode@19:c>e<cgi_decode@19:c><cgi_decode@19:c><cgi_decode@19:c><cgi_decode@19:c>a<cgi_decode@19:c>s=<cgi_decode@19:c><cgi_decode@19:c>1&ma<cgi_decode@19:c><cgi_decode@19:c>=<cgi_decode@19:c><cgi_decode@19:c><cgi_decode@19:c>2<cgi_decode@23:digit_low>+2+%<cgi_decode@23:digit_high><cgi_decode@23:digit_low>+<cgi_decode@19:c>&',
  '<__init__@15:self><cgi_decode@19:c><cgi_decode@19:c><cgi_decode@19:c><cgi_decode@19:c><cgi_decode@19:c><cgi_decode@19:c>e<cgi_decode@19:c><cgi_decode@19:c><cgi_decode@19:c><cgi_decode@19:c>at<cgi_decode@19:c>s=<cgi_decode@19:c><cgi_decode@19:c>od&status=<cgi_decode@19:c>a<cgi_decode@19:c>p<cgi_decode@19:c>&',
  '<__init__@15:self><cgi_decode@19:c><cgi_decode@19:c>l<cgi_decode@19:c><cgi_decode@19:c><cgi_decode@23:digit_high><cgi_decode@23:digit_low><cgi_decode@19:c><cgi_decode@19:c>o<cgi_decode@19:c>l<cgi_decode@19:c>%2<cgi_decode@23:digit_low>',
  '<__init__@15:self><cgi_decode@19:c><cgi_decode@19:c>o<cgi_decode@19:c><cgi_decode@19:c><cgi_decode@23:digit_high><cgi_decode@23:digit_low>%<cgi_decode@23:digit_high><cgi_decode@23:digit_low>%20<cgi_decode@19:c><cgi_decode@19:c><cgi_decode@19:c><cgi_decode@19:c>%20%23%20<cgi_decode@19:c><cgi_decode@19:c><cgi_decode@19:c><cgi_decode@19:c>en<cgi_decode@19:c>%20%2<cgi_decode@23:digit_low>',
  '<__init__@15:self><cgi_decode@19:c><cgi_decode@23:digit_high><cgi_decode@23:digit_low><cgi_decode@19:c><cgi_decode@19:c>%22<cgi_decode@19:c><cgi_decode@19:c>%2<cgi_decode@23:digit_low><cgi_decode@19:c><cgi_decode@19:c>%2<cgi_decode@23:digit_low><cgi_decode@19:c><cgi_decode@19:c>%2<cgi_decode@23:digit_low><cgi_decode@19:c>J%2<cgi_decode@23:digit_low><cgi_decode@19:c>B%2<cgi_decode@23:digit_low><cgi_decode@19:c><cgi_decode@19:c>%2<cgi_decode@23:digit_low><cgi_decode@19:c><cgi_decode@19:c>%2<cgi_decode@23:digit_low><cgi_decode@19:c><cgi_decode@19:c>%2<cgi_decode@23:digit_low><cgi_decode@19:c>',
  '<__init__@15:self><cgi_decode@19:c><cgi_decode@23:digit_high><cgi_decode@23:digit_low><cgi_decode@19:c><cgi_decode@19:c>%2<cgi_decode@23:digit_low><cgi_decode@19:c><cgi_decode@19:c>%2<cgi_decode@23:digit_low><cgi_decode@19:c>N%2<cgi_decode@23:digit_low><cgi_decode@19:c>V%2<cgi_decode@23:digit_low><cgi_decode@19:c><cgi_decode@19:c>%2<cgi_decode@23:digit_low><cgi_decode@19:c><cgi_decode@19:c>%2<cgi_decode@23:digit_low>Ae%2<cgi_decode@23:digit_low><cgi_decode@19:c><cgi_decode@19:c>%2<cgi_decode@23:digit_low><cgi_decode@19:c>f%2EB',
  '<__init__@15:self><cgi_decode@19:c><cgi_decode@23:digit_high><cgi_decode@23:digit_low><cgi_decode@19:c><cgi_decode@19:c>%3<cgi_decode@23:digit_low><cgi_decode@19:c><cgi_decode@19:c>%3<cgi_decode@23:digit_low><cgi_decode@19:c><cgi_decode@19:c>%<cgi_decode@23:digit_high><cgi_decode@23:digit_low><cgi_decode@19:c><cgi_decode@19:c>%<cgi_decode@23:digit_high><cgi_decode@23:digit_low><cgi_decode@19:c>h%5<cgi_decode@23:digit_low><cgi_decode@19:c><cgi_decode@19:c>%5<cgi_decode@23:digit_low><cgi_decode@19:c>D%5<cgi_decode@23:digit_low>DR%5<cgi_decode@23:digit_low>c<cgi_decode@19:c>%5<cgi_decode@23:digit_low><cgi_decode@19:c>',
  '<__init__@15:self><cgi_decode@19:c><cgi_decode@23:digit_high><cgi_decode@23:digit_low><cgi_decode@19:c><cgi_decode@19:c>%5<cgi_decode@23:digit_low><cgi_decode@19:c><cgi_decode@19:c>%5<cgi_decode@23:digit_low><cgi_decode@19:c><cgi_decode@19:c>%5<cgi_decode@23:digit_low><cgi_decode@19:c><cgi_decode@19:c>%<cgi_decode@23:digit_high><cgi_decode@23:digit_low><cgi_decode@19:c><cgi_decode@19:c>%<cgi_decode@23:digit_high>b<cgi_decode@19:c><cgi_decode@19:c>%7<cgi_decode@23:digit_low>h<cgi_decode@19:c>%7<cgi_decode@23:digit_low>mB%7e<cgi_decode@19:c>c%7B<cgi_decode@19:c>',
  '<__init__@15:self><cgi_decode@19:c><cgi_decode@23:digit_high><cgi_decode@23:digit_low><cgi_decode@19:c><cgi_decode@19:c>%7<cgi_decode@23:digit_low>C<cgi_decode@19:c>%7<cgi_decode@23:digit_low><cgi_decode@19:c>',
  '<__init__@15:self><cgi_decode@19:c><cgi_decode@23:digit_high><cgi_decode@23:digit_low><cgi_decode@19:c><cgi_decode@19:c>%<cgi_decode@23:digit_high><cgi_decode@23:digit_low><cgi_decode@19:c>F%3<cgi_decode@23:digit_low><cgi_decode@19:c><cgi_decode@19:c>%3<cgi_decode@23:digit_low><cgi_decode@19:c><cgi_decode@19:c>%3<cgi_decode@23:digit_low><cgi_decode@19:c><cgi_decode@19:c>%3<cgi_decode@23:digit_low><cgi_decode@19:c><cgi_decode@19:c>%3<cgi_decode@23:digit_low><cgi_decode@19:c><cgi_decode@19:c>%3Ay<cgi_decode@19:c>%3B<cgi_decode@19:c>q%3C<cgi_decode@19:c>',
  '<__init__@15:self><cgi_decode@19:c>t<cgi_decode@19:c><cgi_decode@19:c><cgi_decode@19:c>/t<cgi_decode@19:c><cgi_decode@19:c><cgi_decode@19:c><cgi_decode@19:c>t/<cgi_decode@19:c><cgi_decode@19:c>g<cgi_decode@19:c><cgi_decode@19:c><cgi_decode@19:c>a<cgi_decode@19:c>p<cgi_decode@19:c><cgi_decode@19:c>seri<cgi_decode@19:c><cgi_decode@19:c><cgi_decode@19:c>ob<cgi_decode@19:c><cgi_decode@23:digit_high><cgi_decode@23:digit_low>%<cgi_decode@23:digit_high>b%2<cgi_decode@23:digit_low>update%20logintable%20set%20pass<cgi_decode@19:c>d%3d%270wn3d%27%3b<cgi_decode@19:c>-%00',
  '<__init__@15:self><cgi_decode@19:c>t<cgi_decode@19:c><cgi_decode@19:c><cgi_decode@19:c>/t<cgi_decode@19:c><cgi_decode@19:c><cgi_decode@19:c><cgi_decode@19:c>t/get<cgi_decode@19:c>ata<cgi_decode@19:c>php<cgi_decode@19:c>data<cgi_decode@19:c><cgi_decode@19:c><cgi_decode@23:digit_high><cgi_decode@23:digit_low><cgi_decode@19:c>cr<cgi_decode@19:c>pt%<cgi_decode@23:digit_high><cgi_decode@23:digit_low>src=%22<cgi_decode@31:t>tp%3a%2<cgi_decode@23:digit_low>%2f',
  '<__init__@15:self><cgi_decode@31:t><cgi_decode@19:c><cgi_decode@19:c><cgi_decode@19:c><cgi_decode@19:c><cgi_decode@19:c><cgi_decode@19:c>a<cgi_decode@19:c><cgi_decode@19:c>.c<cgi_decode@19:c><cgi_decode@19:c><cgi_decode@19:c><cgi_decode@23:digit_high><cgi_decode@23:digit_low><cgi_decode@19:c>a<cgi_decode@19:c><cgi_decode@19:c><cgi_decode@19:c>.<cgi_decode@19:c>s%22%<cgi_decode@23:digit_high>e%3c%2fsc<cgi_decode@19:c><cgi_decode@19:c>pt%3e',
  '<cgi_decode@19:c>',
  '<cgi_decode@23:digit_low>',
  'C',
  'H',
  'O',
  'S',
  'W',
  'a',
  'h',
  'n',
  'w',
  'y'],
 '<__init__@15:self>': ['<cgi_decode@19:c>', '<cgi_decode@31:t>'],
 '<cgi_decode@19:c>': ['%', '+', '<__add__@1115:other>', '<create@27:self>'],
 '<cgi_decode@23:digit_high>': ['2',
  '3',
  '4',
  '5',
  '6',
  '7',
  '<cgi_decode@19:c>',
  '<cgi_decode@23:digit_low>'],
 '<cgi_decode@23:digit_low>': ['0',
  '1',
  '2',
  '3',
  '4',
  '5',
  '6',
  '7',
  '8',
  '9',
  '<cgi_decode@19:c>',
  '<cgi_decode@23:digit_high>',
  'A',
  'B',
  'C',
  'D',
  'E',
  'F',
  'a',
  'b',
  'c',
  'd',
  'e',
  'f'],
 '<cgi_decode@31:t>': ['<__add__@1115:other>',
  '<__add__@1115:other>w',
  '<__add__@1115:self>',
  'h<__add__@1115:other>'],
 '<__add__@1115:other>': ['&',
  '-',
  '.',
  '/',
  '0',
  '1',
  '2',
  '3',
  '4',
  '5',
  '6',
  '7',
  '8',
  '9',
  ':',
  '<__add__@1115:self>',
  '<cgi_decode@19:c>',
  '<cgi_decode@23:digit_high>',
  '<cgi_decode@23:digit_low>',
  '=',
  '?',
  'A',
  'B',
  'C',
  'D',
  'E',
  'F',
  'G',
  'H',
  'I',
  'J',
  'K',
  'L',
  'M',
  'N',
  'O',
  'P',
  'Q',
  'R',
  'S',
  'T',
  'U',
  'V',
  'W',
  'X',
  'Y',
  'Z',
  '_',
  'a',
  'b',
  'c',
  'd',
  'e',
  'f',
  'g',
  'h',
  'i',
  'j',
  'k',
  'l',
  'm',
  'n',
  'o',
  'p',
  'q',
  'r',
  's',
  't',
  'u',
  'v',
  'w',
  'x',
  'y',
  'z',
  '~'],
 '<__add__@1115:self>': ['<__add__@1115:other>', '<create@27:self>']}
In [248]:
(460, 1000)
In [249]:
(380, 1000)

2.2.2  Calculator

2.2.2.1  Golden Grammar

In [250]:

2.2.2.2  Samples

In [251]:
In [252]:
CPU times: user 332 ms, sys: 387 ms, total: 719 ms
Wall time: 6.72 s

2.2.2.3  Mimid

In [253]:
Out[253]:
{'<START>': ['<parse_expr-0-c>'],
 '<parse_expr-0-c>': ['<parse_expr-1>', '<parse_expr-2-s><parse_expr-1>'],
 '<parse_expr-1>': ['(<parse_expr-0-c>)', '<parse_num-1-s>'],
 '<parse_expr-2-s>': ['<parse_expr-1><parse_expr>',
  '<parse_expr-1><parse_expr><parse_expr-2-s>'],
 '<parse_num-1-s>': ['<is_digit-0-c>', '<is_digit-0-c><parse_num-1-s>'],
 '<is_digit-0-c>': ['0', '1', '2', '3', '4', '5', '6', '7', '8', '9'],
 '<parse_expr>': ['*', '+', '-', '/']}
In [254]:
(1000, 1000)
In [255]:
In [256]:
(1000, 1000)

2.2.2.4  Autogram

In [257]:
CPU times: user 9.24 ms, sys: 6.19 ms, total: 15.4 ms
Wall time: 6.55 s
In [258]:
Out[258]:
{'<START>': ['<__init__@15:self>'],
 '<__init__@15:self>': ['<parse_expr@26:c>00',
  '<parse_expr@26:c>1+2)<parse_expr@26:c><parse_expr@26:c><parse_expr@26:c>(423<parse_expr@26:c>334+9983)-<parse_expr@26:c>-((6)-(701))',
  '<parse_expr@26:c>100)',
  '<parse_expr@26:c>12<parse_expr@26:c><parse_expr@26:c>1<parse_expr@29:num>*(12-3)/9+8)+33',
  '<parse_expr@26:c>1<parse_expr@26:c><parse_expr@26:c>',
  '<parse_expr@26:c>1<parse_expr@26:c><parse_expr@26:c>0<parse_expr@26:c>2',
  '<parse_expr@26:c>3<parse_expr@26:c><parse_expr@26:c>4<parse_expr@26:c><parse_expr@26:c>',
  '<parse_expr@26:c>3<parse_expr@26:c><parse_expr@29:num><parse_expr@26:c>*<parse_expr@29:num>*4',
  '<parse_expr@26:c>4<parse_expr@26:c><parse_expr@26:c><parse_expr@29:num><parse_expr@26:c>33-<parse_expr@26:c>22',
  '<parse_expr@26:c>55<parse_expr@26:c><parse_expr@26:c>234-445)',
  '<parse_expr@26:c><parse_expr@26:c><parse_expr@26:c>',
  '<parse_expr@26:c><parse_expr@26:c><parse_expr@26:c>41/2)'],
 '<parse_expr@26:c>': ['(',
  '*',
  '+',
  '-',
  '/',
  '1',
  '2',
  '3',
  '4',
  '5',
  '<parse_expr@29:num>'],
 '<parse_expr@29:num>': ['1', '2', '22', '23', '3', '33', '4', '5']}
In [259]:
(395, 1000)
In [260]:
(1, 1000)

2.2.3  MathExpr

2.2.3.1  Golden Grammar

In [261]:

2.2.3.2  Samples

In [262]:

2.2.3.3  Mimid

In [263]:
CPU times: user 1.03 s, sys: 922 ms, total: 1.95 s
Wall time: 17 s
In [264]:
Out[264]:
{'<START>': ['<parseAddition-1>'],
 '<parseAddition-1>': ['<parseMultiplication-1>',
  '<parseMultiplication-1><parseAddition-2-s>'],
 '<parseMultiplication-1>': ['<parseParenthesis-0-c>',
  '<parseParenthesis-0-c><parseMultiplication-2-s>'],
 '<parseAddition-2-s>': ['<parseAddition>',
  '<parseAddition><parseAddition-2-s>'],
 '<parseParenthesis-0-c>': [' <parseNegative-0-c>',
  '(<parseAddition-1>)',
  '<parseNegative-0-c>'],
 '<parseMultiplication-2-s>': ['<parseMultiplication>',
  '<parseMultiplication><parseMultiplication-2-s>'],
 '<parseNegative-0-c>': ['-<parseParenthesis-0-c>', '<parseValue-0-c>'],
 '<parseValue-0-c>': ['<parseNumber-1-s>', '<parseVariable-0-c>'],
 '<parseNumber-1-s>': ['<parseNumber>', '<parseNumber><parseNumber-1-s>'],
 '<parseVariable-0-c>': ['a',
  'a<parseVariable-9-c>',
  'b',
  'c',
  'co<parseVariable-11>',
  'e',
  'exp<parseArguments-1>',
  'hypot<parseArguments-1>',
  'p<parseVariable-1-c>',
  'x'],
 '<parseNumber>': ['.', '0', '1', '2', '3', '4', '5', '6', '7', '8', '9'],
 '<parseVariable-9-c>': ['b<parseVariable-11>', 'tan2<parseArguments-1>'],
 '<parseVariable-11>': ['s<parseArguments-1>'],
 '<parseArguments-1>': ['(<parseAddition-1><parseArguments-2-c>'],
 '<parseVariable-1-c>': ['i', 'ow<parseArguments-1>'],
 '<parseArguments-2-c>': [')', ', <parseAddition-1>)'],
 '<parseMultiplication>': ['<parseMultiplication-2>',
  '<parseMultiplication-3>',
  '<parseMultiplication-5>'],
 '<parseMultiplication-2>': ['*<parseParenthesis-0-c>'],
 '<parseMultiplication-3>': [' ', ' <parseMultiplication-4>'],
 '<parseMultiplication-5>': ['/<parseParenthesis-0-c>'],
 '<parseMultiplication-4>': ['<parseMultiplication-2>',
  '<parseMultiplication-5>'],
 '<parseAddition>': ['+<parseMultiplication-1>', '-<parseMultiplication-1>']}
In [265]:
(699, 1000)
In [266]:
In [267]:
(922, 1000)

2.2.3.4  Autogram

In [268]:
CPU times: user 11.4 ms, sys: 9.45 ms, total: 20.8 ms
Wall time: 26.5 s
In [269]:
Out[269]:
{'<START>': ['<hasnext@61:self.string>'],
 '<hasnext@61:self.string>': ['<parseparenthesis@137:char> <parsemultiplication@111:char> 2 * 3',
  '<parseparenthesis@137:char> <parsemultiplication@111:char> pi / 4',
  '<parseparenthesis@137:char>(1 + 2) <parsemultiplication@111:char> 3',
  '<parseparenthesis@137:char>.0 <parsemultiplication@111:char> 3 <parsemultiplication@111:char> 6',
  '<parseparenthesis@137:char>00',
  '<parseparenthesis@137:char>1 + 2) <parsemultiplication@111:char> 3',
  '<parseparenthesis@137:char>1 - 1 + -1) <parsemultiplication@111:char> pi',
  '<parseparenthesis@137:char>1-2)<parsemultiplication@111:char>3.0 <parsemultiplication@111:char> 0.0000',
  '<parseparenthesis@137:char>100)',
  '<parseparenthesis@137:char>123<parsemultiplication@111:char>133*(12-3)/9+8)+33',
  '<parseparenthesis@137:char>1<parsemultiplication@111:char>20<parsemultiplication@111:char>2',
  '<parseparenthesis@137:char>3<parsemultiplication@111:char>234*22*4',
  '<parseparenthesis@137:char>43<parsemultiplication@111:char>334<parseaddition@93:char>33-222',
  '<parseparenthesis@137:char>55<parsemultiplication@111:char>(234-445)',
  '<parseparenthesis@137:char><parsemultiplication@111:char>(41/2)',
  '<parseparenthesis@137:char><parsemultiplication@111:char>2',
  '<parseparenthesis@137:char>a + b) <parsemultiplication@111:char> c',
  '<parseparenthesis@137:char>bs(-2) <parsemultiplication@111:char> pi / 4',
  '<parseparenthesis@137:char>i <parsemultiplication@111:char> e',
  '<parseparenthesis@137:char>os(pi) <parsemultiplication@111:char> 1',
  '<parseparenthesis@137:char>os(x<parsemultiplication@111:char>4*3) + 2 * 3',
  '<parseparenthesis@137:char>ow(3, 5)',
  '<parseparenthesis@137:char>pi + e * 10) <parsemultiplication@111:char> 10',
  '<parseparenthesis@137:char>pi<parsemultiplication@111:char>e+2)*3<parsemultiplication@111:char>(423<parsemultiplication@111:char>334+9983)-5-((6)-(701-x))',
  '<parseparenthesis@137:char>tan2(2, 1)',
  '<parseparenthesis@137:char>x + e * 10) <parsemultiplication@111:char> 10',
  '<parseparenthesis@137:char>xp(0)',
  '<parseparenthesis@137:char>ypot(5, 12)'],
 '<parseparenthesis@137:char>': ['(',
  '-',
  '1',
  '2',
  '3',
  '4',
  '5',
  'a',
  'c',
  'e',
  'h',
  'p'],
 '<parsemultiplication@111:char>': ['*', '/', '<parseaddition@93:char>'],
 '<parseaddition@93:char>': ['+', '-']}
In [270]:
(301, 1000)
In [271]:
(0, 1000)

2.2.4  URLParse

2.2.4.1  Golden Grammar

In [272]:

2.2.4.2  Samples

In [273]:

Unfortunately, as we detail in the paper, both the miners are unable to generalize well with the kind of inputs above. The problem is the lack of generalization of string tokens. Hence we use the ones below, which are generated using the golden grammar. This is the output of simply using the golden grammar to fuzz and generate 100 inputs. Captured here for deterministic reproduction.

In [274]:

2.2.4.3  Mimid

In [275]:
CPU times: user 356 ms, sys: 265 ms, total: 621 ms
Wall time: 6.13 s
In [276]:
Out[276]:
{'<START>': ['<urlparse-1>'],
 '<urlparse-1>': ['<urlsplit-1>', '<urlsplit-1>/'],
 '<urlsplit-1>': ['<urlsplit-7>', '<urlsplit-7><urlsplit-1-c>'],
 '<urlsplit-7>': ['<urlsplit-20>', 'f', 'http:<urlsplit-18>', 'https'],
 '<urlsplit-1-c>': ['://<urlsplit-16>',
  'host1:40',
  'host2',
  'host4:10',
  'host5:50',
  's<urlsplit-8-c>',
  'tp://<urlsplit-16>',
  'tp<urlsplit-13-c>',
  'tps<urlsplit-4-c>'],
 '<urlsplit-20>': ['http', 'http://<_splitnetloc-0-c>'],
 '<urlsplit-18>': ['//', '//<urlsplit-19>'],
 '<_splitnetloc-0-c>': ['host1',
  'host1/folder//',
  'host1/folder//folder',
  'host1:10/folder/',
  'host2',
  'host2/folder//folder',
  'host2:10',
  'host2:50',
  'host3',
  'host3/folder',
  'host3/folder//folder//folder',
  'host3:10/folder/',
  'host3:30',
  'host3:40',
  'host4',
  'host4:10',
  'host4:30',
  'host4:30/folder',
  'host4:40',
  'host5',
  'host5/folder',
  'host5/folder//',
  'host5:30',
  'host5:40/folder',
  'user1:pass1@host1:10',
  'user1:pass1@host5:20',
  'user1:pass3@host3:10/folder/',
  'user1:pass3@host4',
  'user1:pass4@host1/folder',
  'user1:pass4@host5',
  'user2:pass1@host5:10/folder//',
  'user2:pass2@host3',
  'user2:pass2@host4:10/folder//folder//folder/',
  'user2:pass2@host4:20',
  'user2:pass2@host5:50',
  'user2:pass3@host4:50',
  'user2:pass4@host2',
  'user2:pass4@host4:40',
  'user2:pass4@host5:50/folder',
  'user2:pass5@host2',
  'user2:pass5@host3:30',
  'user2:pass5@host5:40',
  'user2:pass5@host5:50',
  'user3:pass2@host1/folder//',
  'user3:pass3@host1:40',
  'user3:pass3@host2:20/folder',
  'user3:pass3@host2:40',
  'user3:pass3@host5',
  'user3:pass4@host2:20',
  'user3:pass5@host4',
  'user4:pass2@host1',
  'user4:pass2@host2:30',
  'user4:pass3@host1/folder',
  'user4:pass3@host3/folder',
  'user4:pass3@host3:50',
  'user4:pass4@host2:50/folder/',
  'user4:pass4@host5/folder',
  'user4:pass5@host1',
  'user4:pass5@host2',
  'user4:pass5@host3',
  'user4:pass5@host4/folder//folder//folder/',
  'user4:pass5@host4:50',
  'user5:pass1@host3:50',
  'user5:pass2@host4/folder//',
  'user5:pass3@host1',
  'user5:pass3@host1:10',
  'user5:pass3@host4:40',
  'user5:pass5@host2:10/folder',
  'user5:pass5@host4'],
 '<urlsplit-19>': ['<_splitnetloc-0-c>', '<_splitnetloc-0-c><urlsplit-2>'],
 '<urlsplit-2>': ['/folder//?key4=value4&key3=value3',
  '/folder/?key2=value2',
  '/folder/?key2=value2&key2=value3&key3=value4',
  '/folder/?key3=value1&key2=value4',
  '/folder?key1=value4&key4=value2&key2=value1&key2=value3',
  '/folder?key2=value2',
  '/folder?key4=value3&key4=value2',
  '?key3=value3&key2=value2'],
 '<urlsplit-16>': ['<_splitnetloc-0-c>', '<_splitnetloc-0-c>/<urlsplit>'],
 '<urlsplit-8-c>': ['://host2',
  '://host2:30',
  '://host3:10',
  '://user1:pass1@host3:50',
  '://user1:pass4@host4',
  '://user3:pass4@host1:20',
  '<urlsplit-9>'],
 '<urlsplit-13-c>': ['://user5:pass2@host3', '<urlsplit-9>'],
 '<urlsplit-4-c>': ['://<urlsplit-6>', '://user5:pass3@host3:30'],
 '<urlsplit>': ['/?key1=value1&key4=value3',
  '/?key1=value3',
  '/?key1=value4',
  '/?key3=value1',
  '/folder//?key1=value3',
  '/folder//?key4=value2',
  '/folder/?key3=value2&key2=value4&key1=value3&key3=value2',
  '/folder/?key4=value1&key1=value4',
  '/folder?key2=value1&key3=value2&key1=value4&key3=value4&key3=value1&key1=value2&key1=value2',
  '/folder?key2=value3',
  '/folder?key3=value1',
  '/folder?key3=value2&key2=value1&key2=value2&key4=value3&key3=value3&key3=value1',
  '/folder?key3=value3',
  '/folder?key3=value3&key4=value4&key2=value2',
  '/folder?key4=value2',
  '?key1=value1&key2=value3&key3=value2&key2=value3&key4=value2&key2=value3',
  '?key1=value2&key1=value1',
  '?key1=value3',
  '?key1=value3&key3=value3&key3=value1',
  '?key1=value4&key1=value1&key2=value1&key2=value1',
  '?key2=value4&key1=value2&key3=value3&key3=value2&key4=value3',
  '?key2=value4&key2=value4&key4=value1&key2=value2&key2=value3&key4=value1',
  '?key3=value1',
  '?key3=value1&key1=value3',
  '?key3=value2',
  '?key3=value2&key1=value4',
  '?key3=value3',
  '?key3=value3&key4=value1',
  '?key4=value1',
  '?key4=value2',
  '?key4=value2&key1=value2&key4=value3&key2=value4',
  '?key4=value4'],
 '<urlsplit-9>': ['://<urlsplit-10>'],
 '<urlsplit-10>': ['<_splitnetloc-0-c>', '<_splitnetloc-0-c><urlsplit>'],
 '<urlsplit-6>': ['<_splitnetloc-0-c>', '<_splitnetloc-0-c><urlsplit-6-c>'],
 '<urlsplit-6-c>': ['/', '<urlsplit>']}
In [277]:
(1000, 1000)
In [278]:
In [279]:
(153, 1000)

2.2.4.4  Autogram

In [280]:
CPU times: user 12.7 ms, sys: 6.55 ms, total: 19.3 ms
Wall time: 48 s
In [281]:
Out[281]:
{'<START>': ['<create@27:self>'],
 '<create@27:self>': ['<__init__@15:self>:<__init__@1047:self._ostr>',
  '<__init__@15:self>:<create@27:self>',
  '<__init__@15:self><__init__@1047:self._ostr>',
  '<__init__@15:self><__init__@1047:self._ostr>/',
  '<__init__@15:self><__init__@1047:self._ostr><urlsplit@434:url>',
  '<__init__@15:self><__init__@1047:self._ostr><urlsplit@458:url>',
  '<__init__@15:self>?<_split_helper@1259:item>',
  '?<_split_helper@1259:item>'],
 '<__init__@15:self>': ['//',
  '<__new__@1:path>/',
  '<__new__@1:scheme>',
  '<_split_helper@1259:item>',
  '<urlsplit@434:url>/',
  '<urlsplit@446:c><urlsplit@446:c><urlsplit@446:c>',
  '<urlsplit@446:c><urlsplit@446:c><urlsplit@446:c><urlsplit@446:c>',
  '<urlsplit@446:c><urlsplit@446:c>t<urlsplit@446:c><urlsplit@446:c>',
  '<urlsplit@458:url>/'],
 '<__init__@1047:self._ostr>': ['<__new__@1:netloc>', '<create@27:self>'],
 '<urlsplit@434:url>': ['<__new__@1:path>', '<create@27:self>'],
 '<urlsplit@458:url>': ['<__new__@1:path>', '<create@27:self>'],
 '<_split_helper@1259:item>': ['/', '<__new__@1:path>', '<__new__@1:query>'],
 '<__new__@1:path>': ['/',
  '/folder',
  '/folder/',
  '/folder//',
  '/folder//folder',
  '/folder//folder//folder',
  '/folder//folder//folder/',
  '<__new__@1:path>'],
 '<__new__@1:scheme>': ['<__new__@1:scheme>', 'http'],
 '<urlsplit@446:c>': ['f', 'h', 'p', 's', 't'],
 '<__new__@1:netloc>': ['host1',
  'host1:10',
  'host1:40',
  'host2',
  'host2:10',
  'host2:30',
  'host2:50',
  'host3',
  'host3:10',
  'host3:30',
  'host3:40',
  'host4',
  'host4:10',
  'host4:30',
  'host4:40',
  'host5',
  'host5:30',
  'host5:40',
  'host5:50',
  'user1:pass1@host1:10',
  'user1:pass1@host3:50',
  'user1:pass1@host5:20',
  'user1:pass3@host3:10',
  'user1:pass3@host4',
  'user1:pass4@host1',
  'user1:pass4@host4',
  'user1:pass4@host5',
  'user2:pass1@host5:10',
  'user2:pass2@host3',
  'user2:pass2@host4:10',
  'user2:pass2@host4:20',
  'user2:pass2@host5:50',
  'user2:pass3@host4:50',
  'user2:pass4@host2',
  'user2:pass4@host4:40',
  'user2:pass4@host5:50',
  'user2:pass5@host2',
  'user2:pass5@host3:30',
  'user2:pass5@host5:40',
  'user2:pass5@host5:50',
  'user3:pass2@host1',
  'user3:pass3@host1:40',
  'user3:pass3@host2:20',
  'user3:pass3@host2:40',
  'user3:pass3@host5',
  'user3:pass4@host1:20',
  'user3:pass4@host2:20',
  'user3:pass5@host4',
  'user4:pass2@host1',
  'user4:pass2@host2:30',
  'user4:pass3@host1',
  'user4:pass3@host3',
  'user4:pass3@host3:50',
  'user4:pass4@host2:50',
  'user4:pass4@host5',
  'user4:pass5@host1',
  'user4:pass5@host2',
  'user4:pass5@host3',
  'user4:pass5@host4',
  'user4:pass5@host4:50',
  'user5:pass1@host3:50',
  'user5:pass2@host3',
  'user5:pass2@host4',
  'user5:pass3@host1',
  'user5:pass3@host1:10',
  'user5:pass3@host3:30',
  'user5:pass3@host4:40',
  'user5:pass5@host2:10',
  'user5:pass5@host4'],
 '<__new__@1:query>': ['<__new__@1:query>',
  'key1=value1&key2=value3&key3=value2&key2=value3&key4=value2&key2=value3',
  'key1=value1&key4=value3',
  'key1=value2&key1=value1',
  'key1=value3',
  'key1=value3&key3=value3&key3=value1',
  'key1=value4',
  'key1=value4&key1=value1&key2=value1&key2=value1',
  'key1=value4&key4=value2&key2=value1&key2=value3',
  'key2=value1&key3=value2&key1=value4&key3=value4&key3=value1&key1=value2&key1=value2',
  'key2=value2',
  'key2=value2&key2=value3&key3=value4',
  'key2=value3',
  'key2=value4&key1=value2&key3=value3&key3=value2&key4=value3',
  'key2=value4&key2=value4&key4=value1&key2=value2&key2=value3&key4=value1',
  'key3=value1',
  'key3=value1&key1=value3',
  'key3=value1&key2=value4',
  'key3=value2',
  'key3=value2&key1=value4',
  'key3=value2&key2=value1&key2=value2&key4=value3&key3=value3&key3=value1',
  'key3=value2&key2=value4&key1=value3&key3=value2',
  'key3=value3',
  'key3=value3&key2=value2',
  'key3=value3&key4=value1',
  'key3=value3&key4=value4&key2=value2',
  'key4=value1',
  'key4=value1&key1=value4',
  'key4=value2',
  'key4=value2&key1=value2&key4=value3&key2=value4',
  'key4=value3&key4=value2',
  'key4=value4',
  'key4=value4&key3=value3']}
In [282]:
(1000, 1000)
In [283]:
(277, 1000)

2.2.5  Netrc

2.2.5.1  Golden Grammar

In [284]:

2.2.5.2  Samples

In [285]:

As with urlparse, we had to use a restricted set of keywords with netrc. The below words are produced from fuzzing the golden grammar, captured here for deterministic reproduction.

In [286]:

2.2.5.3  Mimid

In [287]:
CPU times: user 1.23 s, sys: 1.72 s, total: 2.95 s
Wall time: 30.4 s
In [288]:
Out[288]:
{'<START>': ['<_parse__netrc-0-c>'],
 '<_parse__netrc-0-c>': ['<_parse__netrc-29>',
  'machine <_parse__netrc-22><_parse__netrc-59><_parse__netrc-29>',
  'machine m2 password pwd3 machine m2 <_parse__netrc-23>password pwd2'],
 '<_parse__netrc-29>': ['machine <_parse__netrc-67><_parse__netrc-32>',
  'machine <_parse__netrc-67><_parse__netrc-56>'],
 '<_parse__netrc-22>': ['m1 ', 'm3 '],
 '<_parse__netrc-59>': ['<_parse__netrc-60>',
  '<_parse__netrc-64><_parse__netrc-65>'],
 '<_parse__netrc-23>': ['account a1 ', 'login l3 ', 'password pwd3 '],
 '<_parse__netrc-67>': ['m1 ', 'm2 ', 'm3 '],
 '<_parse__netrc-32>': ['<_parse__netrc-34><_parse__netrc-35>',
  '<_parse__netrc-47><_parse__netrc-48>',
  '<_parse__netrc>'],
 '<_parse__netrc-56>': ['<_parse__netrc-8>',
  '<_parse__netrc-8><_parse__netrc-56>'],
 '<_parse__netrc-34>': ['<_parse__netrc-5>',
  '<_parse__netrc-5><_parse__netrc-34>'],
 '<_parse__netrc-35>': ['<_parse__netrc-37><_parse__netrc-38>',
  '<_parse__netrc>'],
 '<_parse__netrc-47>': ['<_parse__netrc-8>',
  '<_parse__netrc-8><_parse__netrc-47>'],
 '<_parse__netrc-48>': ['<_parse__netrc-16>',
  '<_parse__netrc-50><_parse__netrc-51>'],
 '<_parse__netrc>': ['password <_parse__netrc-19>'],
 '<_parse__netrc-5>': ['account <_parse__netrc-28>',
  'login <_parse__netrc-27>'],
 '<_parse__netrc-28>': ['a1 ', 'a2 ', 'a3 '],
 '<_parse__netrc-27>': ['l1 ', 'l2 ', 'l3 '],
 '<_parse__netrc-37>': ['<_parse__netrc-8>',
  '<_parse__netrc-8><_parse__netrc-37>'],
 '<_parse__netrc-38>': ['<_parse__netrc-16>',
  '<_parse__netrc-40><_parse__netrc-41>'],
 '<_parse__netrc-8>': ['password <_parse__netrc-2>'],
 '<_parse__netrc-2>': ['pwd1', 'pwd1 ', 'pwd2', 'pwd2 ', 'pwd3', 'pwd3 '],
 '<_parse__netrc-16>': ['<_parse__netrc>',
  'account <_parse__netrc-20>',
  'login <_parse__netrc-9>'],
 '<_parse__netrc-40>': ['<_parse__netrc-5>',
  '<_parse__netrc-5><_parse__netrc-40>'],
 '<_parse__netrc-41>': ['<_parse__netrc-16>',
  '<_parse__netrc-43><_parse__netrc-45><_parse__netrc-16>'],
 '<_parse__netrc-20>': ['a1', 'a2', 'a3'],
 '<_parse__netrc-9>': ['l1', 'l2', 'l3'],
 '<_parse__netrc-43>': ['<_parse__netrc-8>',
  '<_parse__netrc-8><_parse__netrc-43>'],
 '<_parse__netrc-45>': ['<_parse__netrc-5>',
  '<_parse__netrc-5><_parse__netrc-45>'],
 '<_parse__netrc-50>': ['<_parse__netrc-5>',
  '<_parse__netrc-5><_parse__netrc-50>'],
 '<_parse__netrc-51>': ['<_parse__netrc-16>',
  '<_parse__netrc-8><_parse__netrc-16>'],
 '<_parse__netrc-19>': ['pwd1', 'pwd2', 'pwd3'],
 '<_parse__netrc-60>': ['<_parse__netrc-61>',
  '<_parse__netrc-61><_parse__netrc-62>'],
 '<_parse__netrc-64>': ['<_parse__netrc-68>',
  '<_parse__netrc-68><_parse__netrc-64>'],
 '<_parse__netrc-65>': ['<_parse__netrc-4>',
  '<_parse__netrc-4><_parse__netrc-65>'],
 '<_parse__netrc-61>': ['<_parse__netrc-4>',
  '<_parse__netrc-4><_parse__netrc-61>'],
 '<_parse__netrc-62>': ['<_parse__netrc-68>',
  '<_parse__netrc-68><_parse__netrc-62>'],
 '<_parse__netrc-4>': ['password <_parse__netrc-66>'],
 '<_parse__netrc-66>': ['pwd1 ', 'pwd2 ', 'pwd3 '],
 '<_parse__netrc-68>': ['account a3 ', 'login l1 ']}
In [289]:
(773, 1000)
In [290]:
In [291]:
In [292]:
(949, 1000)

2.2.5.4  Autogram

In [293]:
CPU times: user 15.5 ms, sys: 8.65 ms, total: 24.2 ms
Wall time: 2min 59s
In [294]:
Out[294]:
{'<START>': ['<create@27:self>'],
 '<create@27:self>': ['<read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><_parse@47:entryname> <_parse@70:tt> <_parse@108:password>',
  '<read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><_parse@47:entryname> <_parse@70:tt> <_parse@108:password> <_parse@70:tt> <_parse@83:login>',
  '<read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><_parse@47:entryname> <_parse@70:tt> <_parse@108:password> <_parse@70:tt> <_parse@83:login> <_parse@70:tt> <_parse@85:account> login l3 password pwd1',
  '<read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><_parse@47:entryname> <_parse@70:tt> <_parse@108:password> <_parse@70:tt> <_parse@83:login> <create@27:self>chine <_parse@47:entryname> password <_parse@108:password>',
  '<read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><_parse@47:entryname> <_parse@70:tt> <_parse@108:password> <_parse@70:tt> <_parse@83:login> <create@27:self>chine <_parse@47:entryname> password pwd2',
  '<read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><_parse@47:entryname> <_parse@70:tt> <_parse@108:password> <_parse@70:tt> <_parse@83:login> login <_parse@83:login>',
  '<read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><_parse@47:entryname> <_parse@70:tt> <_parse@108:password> <_parse@70:tt> <_parse@83:login> login <_parse@83:login> login <_parse@83:login> <_parse@70:tt> <_parse@85:account>',
  '<read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><_parse@47:entryname> <_parse@70:tt> <_parse@108:password> <_parse@70:tt> <_parse@83:login> password pwd2 password pwd2',
  '<read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><_parse@47:entryname> <_parse@70:tt> <_parse@108:password> <_parse@70:tt> <_parse@85:account>',
  '<read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><_parse@47:entryname> <_parse@70:tt> <_parse@108:password> <_parse@70:tt> <_parse@85:account> account <_parse@85:account>',
  '<read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><_parse@47:entryname> <_parse@70:tt> <_parse@108:password> <_parse@70:tt> <_parse@85:account> account <_parse@85:account> <_parse@70:tt> <_parse@83:login>',
  '<read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><_parse@47:entryname> <_parse@70:tt> <_parse@108:password> <create@27:self>chine m2 <_parse@70:tt> <_parse@85:account> <_parse@70:tt> <_parse@83:login> password pwd3 password <_parse@108:password>',
  '<read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><_parse@47:entryname> <_parse@70:tt> <_parse@108:password> password <_parse@108:password>',
  '<read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><_parse@47:entryname> <_parse@70:tt> <_parse@108:password> password <_parse@108:password> password <_parse@108:password>',
  '<read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><_parse@47:entryname> <_parse@70:tt> <_parse@108:password> password pwd1',
  '<read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><_parse@47:entryname> <_parse@70:tt> <_parse@108:password> password pwd2 password pwd2 <_parse@70:tt> <_parse@85:account>',
  '<read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><_parse@47:entryname> <_parse@70:tt> <_parse@108:password> password pwd3 <create@27:self>chine <_parse@47:entryname> password pwd3',
  '<read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><_parse@47:entryname> <_parse@70:tt> <_parse@108:password> password pwd3 password <_parse@108:password>',
  '<read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><_parse@47:entryname> <_parse@70:tt> <_parse@108:password> password pwd3 password <_parse@108:password> <create@27:self>chine <_parse@47:entryname> password pwd3',
  '<read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><_parse@47:entryname> <_parse@70:tt> <_parse@83:login> <_parse@70:tt> <_parse@108:password>',
  '<read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><_parse@47:entryname> <_parse@70:tt> <_parse@83:login> <_parse@70:tt> <_parse@108:password> <_parse@70:tt> <_parse@85:account>',
  '<read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><_parse@47:entryname> <_parse@70:tt> <_parse@83:login> <_parse@70:tt> <_parse@108:password> login <_parse@83:login> <_parse@70:tt> <_parse@85:account>',
  '<read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><_parse@47:entryname> <_parse@70:tt> <_parse@83:login> <_parse@70:tt> <_parse@108:password> password pwd1',
  '<read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><_parse@47:entryname> <_parse@70:tt> <_parse@83:login> <_parse@70:tt> <_parse@108:password> password pwd2 login <_parse@83:login>',
  '<read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><_parse@47:entryname> <_parse@70:tt> <_parse@83:login> <_parse@70:tt> <_parse@85:account> <_parse@70:tt> <_parse@108:password>',
  '<read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><_parse@47:entryname> <_parse@70:tt> <_parse@83:login> <_parse@70:tt> <_parse@85:account> <_parse@70:tt> <_parse@108:password> login l2 account <_parse@85:account>',
  '<read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><_parse@47:entryname> <_parse@70:tt> <_parse@83:login> <_parse@70:tt> <_parse@85:account> account <_parse@85:account> <_parse@70:tt> <_parse@108:password>',
  '<read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><_parse@47:entryname> <_parse@70:tt> <_parse@83:login> <_parse@70:tt> <_parse@85:account> login <_parse@83:login> <_parse@70:tt> <_parse@108:password>',
  '<read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><_parse@47:entryname> <_parse@70:tt> <_parse@83:login> login <_parse@83:login> <_parse@70:tt> <_parse@108:password>',
  '<read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><_parse@47:entryname> <_parse@70:tt> <_parse@83:login> login <_parse@83:login> <_parse@70:tt> <_parse@85:account> login <_parse@83:login> <_parse@70:tt> <_parse@108:password> password pwd2 password pwd2',
  '<read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><_parse@47:entryname> <_parse@70:tt> <_parse@83:login> login l2 <_parse@70:tt> <_parse@108:password> login l2',
  '<read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><_parse@47:entryname> <_parse@70:tt> <_parse@83:login> login l3 <_parse@70:tt> <_parse@108:password> password pwd1',
  '<read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><_parse@47:entryname> <_parse@70:tt> <_parse@85:account> <_parse@70:tt> <_parse@108:password>',
  '<read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><_parse@47:entryname> <_parse@70:tt> <_parse@85:account> <_parse@70:tt> <_parse@108:password> <_parse@70:tt> <_parse@83:login>',
  '<read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><_parse@47:entryname> <_parse@70:tt> <_parse@85:account> <_parse@70:tt> <_parse@108:password> account <_parse@85:account> password <_parse@108:password> account a3 account a3 account a3',
  '<read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><_parse@47:entryname> <_parse@70:tt> <_parse@85:account> <_parse@70:tt> <_parse@108:password> account a1 password <_parse@108:password>',
  '<read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><_parse@47:entryname> <_parse@70:tt> <_parse@85:account> <_parse@70:tt> <_parse@83:login> account <_parse@85:account> <_parse@70:tt> <_parse@108:password>',
  '<read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><_parse@47:entryname> <_parse@70:tt> <_parse@85:account> account <_parse@85:account> <_parse@70:tt> <_parse@83:login> <_parse@70:tt> <_parse@108:password>',
  '<read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><_parse@47:entryname> <_parse@70:tt> <_parse@85:account> account a1 account <_parse@85:account> <_parse@70:tt> <_parse@108:password> account a1',
  '<read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><read_token@137:nextchar><_parse@47:entryname> <_parse@70:tt> <_parse@85:account> account a3 <_parse@70:tt> <_parse@108:password> <create@27:self>chine <_parse@47:entryname> password <_parse@108:password>',
  'm',
  'ma'],
 '<read_token@137:nextchar>': [' ',
  '<__add__@1115:other>',
  '<create@27:self>'],
 '<_parse@47:entryname>': ['m1', 'm2', 'm3'],
 '<_parse@70:tt>': ['account', 'login', 'password'],
 '<_parse@108:password>': ['pwd1', 'pwd2', 'pwd3'],
 '<_parse@83:login>': ['l1', 'l2', 'l3'],
 '<_parse@85:account>': ['a1', 'a2', 'a3'],
 '<__add__@1115:other>': ['a', 'c', 'e', 'h', 'i', 'n']}
In [295]:
(30, 1000)
In [296]:
(773, 1000)

2.2.6  Microjson

2.2.6.1  Microjson Validation

This is done through json.tar.gz

2.2.6.2  Samples

In [297]:

2.2.6.3  Mimid

In [298]:
CPU times: user 1min 39s, sys: 19.1 s, total: 1min 58s
Wall time: 6min 47s
In [299]:
Out[299]:
{'<START>': ['<_from_json_raw>'],
 '<_from_json_raw>': ['<_from_json_number-1>',
  '<_from_json_raw-3>',
  '<_from_json_raw-4>',
  '<_from_json_raw-5>',
  '<_skip-1-s><_from_json_raw-2>',
  'false',
  'null',
  'true'],
 '<_from_json_number-1>': ['<_from_json_number-1-s>',
  '<_from_json_number-1-s>e<_from_json_number-3-s>'],
 '<_from_json_raw-3>': ['[<_from_json_list-0-c>'],
 '<_from_json_raw-4>': ['{<_from_json_dict-0-c>'],
 '<_from_json_raw-5>': ['"<_from_json_string-0-c>'],
 '<_skip-1-s>': [' ', ' <_skip-1-s>'],
 '<_from_json_raw-2>': ['<_from_json_number-1>',
  '<_from_json_raw-3>',
  '<_from_json_raw-4>',
  '<_from_json_raw-5>',
  'false',
  'null',
  'true'],
 '<_from_json_number-1-s>': ['<_from_json_number>',
  '<_from_json_number><_from_json_number-1-s>'],
 '<_from_json_number-3-s>': ['<_from_json_number>',
  '<_from_json_number><_from_json_number-3-s>'],
 '<_from_json_number>': ['+',
  '-',
  '.',
  '0',
  '1',
  '2',
  '3',
  '4',
  '5',
  '6',
  '7',
  '8',
  '9',
  'E',
  'e'],
 '<_from_json_list-0-c>': ['<_from_json_list-10><_from_json_list-1-c>',
  '<_from_json_list-12>',
  '<_from_json_list-5-s><_from_json_list-6-s><_from_json_list-6-c>'],
 '<_from_json_list-10>': ['<_from_json_raw>', '<_skip-1-s><_from_json_raw>'],
 '<_from_json_list-1-c>': ['<_from_json_list-12>',
  '<_from_json_list-2-s><_from_json_list-12>'],
 '<_from_json_list-12>': ['<_skip-1-s>]', ']'],
 '<_from_json_list-5-s>': ['<_from_json_list-7>',
  '<_from_json_list-7><_from_json_list-5-s>'],
 '<_from_json_list-6-s>': ['<_from_json_list>',
  '<_from_json_list><_from_json_list-6-s>'],
 '<_from_json_list-6-c>': ['<_from_json_list-12>',
  '<_from_json_list-8-s><_from_json_list-9-s><_from_json_list-12>'],
 '<_from_json_list-2-s>': ['<_from_json_list-7>',
  '<_from_json_list-7><_from_json_list-2-s>'],
 '<_from_json_list-7>': ['<_from_json_list-3>',
  '<_from_json_list-4>',
  '<_from_json_raw>'],
 '<_from_json_list-3>': [',<_from_json_raw>'],
 '<_from_json_list-4>': ['<_skip-1-s><_from_json_list-3>'],
 '<_from_json_list>': ['<_from_json_list-3>', '<_from_json_list-4>'],
 '<_from_json_list-8-s>': ['<_from_json_list-7>',
  '<_from_json_list-7><_from_json_list-8-s>'],
 '<_from_json_list-9-s>': ['<_from_json_list>',
  '<_from_json_list><_from_json_list-9-s>'],
 '<_from_json_dict-0-c>': ['<_from_json_dict-1>',
  '<_from_json_dict-3-s><_from_json_dict-1>',
  '<_from_json_dict-5>'],
 '<_from_json_dict-1>': ['<_from_json_dict><_from_json_dict-5>'],
 '<_from_json_dict-3-s>': ['<_from_json_dict><_from_json_dict-7>',
  '<_from_json_dict><_from_json_dict-7><_from_json_dict-3-s>'],
 '<_from_json_dict-5>': ['<_skip-1-s>}', '}'],
 '<_from_json_dict>': ['<_from_json_dict-4>',
  '<_skip-1-s><_from_json_dict-4>'],
 '<_from_json_dict-4>': ['"<_from_json_string-0-c><_from_json_dict-10>'],
 '<_from_json_string-0-c>': ['"', '<_from_json_string-1-s>"'],
 '<_from_json_dict-10>': ['<_from_json_dict-12>',
  '<_skip-1-s><_from_json_dict-12>'],
 '<_from_json_string-1-s>': ['<_from_json_string>',
  '<_from_json_string><_from_json_string-1-s>'],
 '<_from_json_string>': [' ',
  '!',
  '#',
  '$',
  '%',
  '&',
  "'",
  '(',
  ')',
  '*',
  '+',
  ',',
  '-',
  '.',
  '/',
  '0',
  '1',
  '2',
  '3',
  '4',
  '5',
  '6',
  '7',
  '8',
  '9',
  ':',
  ';',
  '<',
  '=',
  '>',
  '?',
  '@',
  'A',
  'B',
  'C',
  'D',
  'E',
  'F',
  'G',
  'H',
  'I',
  'J',
  'K',
  'L',
  'M',
  'N',
  'O',
  'P',
  'Q',
  'R',
  'S',
  'T',
  'U',
  'V',
  'W',
  'X',
  'Y',
  'Z',
  '[',
  '\\<decode_escape-0-c>',
  ']',
  '^',
  '_',
  '`',
  'a',
  'b',
  'c',
  'd',
  'e',
  'f',
  'g',
  'h',
  'i',
  'j',
  'k',
  'l',
  'm',
  'n',
  'o',
  'p',
  'q',
  'r',
  's',
  't',
  'u',
  'v',
  'w',
  'x',
  'y',
  'z',
  '{',
  '|',
  '}',
  '~'],
 '<decode_escape-0-c>': ['"', '/', '\\', 'b', 'f', 'n', 'r', 't'],
 '<_from_json_dict-12>': [':<_from_json_list-10>'],
 '<_from_json_dict-7>': [',', '<_skip-1-s>,']}
In [300]:
(924, 1000)
In [301]:
In [302]:
In [303]:
In [304]:
In [305]:
In [306]:
In [307]:
(93, 100)

2.2.6.4  Autogram

In [308]:
CPU times: user 16.4 ms, sys: 16.6 ms, total: 33 ms
Wall time: 7min 30s
In [309]:
Out[309]:
{'<START>': ['<tell@115:self.buf>'],
 '<tell@115:self.buf>': ['<_skip@76:c>     "JSON Test Pattern pass1",     {"object with 1 member":<_from_json_raw@283:c>"array with 1 element"]},     {},     [],     -42,     true,     false,     null,     {         "integer": 1234567890,         "real": -9876.543210,         "e": 0.123456789e-12,         "E": 1.234567890E+34,         "":  23456789012E66,         "zero": 0,         "one": 1,         "space": " ",         "quote": "\\"",         "backslash": "\\\\",         "controls": "\\b\\f\\n\\r\\t",         "slash": "/ & \\/",         "alpha": "abcdefghijklmnopqrstuvwyz",         "ALPHA": "ABCDEFGHIJKLMNOPQRSTUVWYZ",         "digit": "0123456789",         "0123456789": "digit",         "special": "`1~!@#$%^&*()_+-={\':[,]}|;.<openA>/<closeA>?",         "true": true,         "false": false,         "null": null,         "array":[  ],         "object":{  },         "address": "50 St. James Street",         "url": "http://www.JSON.org/",         "comment": "// /* <!-- --",         "# -- --> */": " ",         " s p a c e d " :[1,2 , 3  ,  4 , 5        ,          6           ,7        ],"compact":[1,2,3,4,5,6,7],         "jsontext": "{\\"object with 1 member\\":[\\"array with 1 element\\"]}",         "quotes": "&#34; %22 0x22 034 &#x22;",         "\\/\\\\\\"\\b\\f\\n\\r\\t`1~!@#$%^&*()_+-=[]{}|;:\',./<openA><closeA>?" : "A key can be any string"     },     0.5 ,98.6 , 99.44 ,  1066, 1e1, 0.1e1, 1e-1, 1e00,2e+00,2e-00 ,"rosebud"]',
  '<_skip@76:c>     "fruit": "<from_json@313:v.fruit>",     "size": "<from_json@313:v.size>",     "color": "<from_json@313:v.color>",     "product": "<from_json@313:v.product>" }',
  '<_skip@76:c>     "quiz": <_from_json_raw@283:c>         "sport": {             "q1": {                 "question": "<from_json@313:v.quiz.sport.q1.question>",                 "options": [                     "New York Bulls",                     "Los Angeles Kings",                     "Golden State Warriros",                     "<from_json@313:v.quiz.sport.q1.answer>"                 ],                 "answer": "Huston Rocket"             }         },         "maths": {             "q1": {                 "question": "<from_json@313:v.quiz.maths.q1.question>",                 "options": [                     "10",                     "11",                     "<from_json@313:v.quiz.maths.q1.answer>",                     "13"                 ],                 "answer": "12"             },             "q2": {                 "question": "<from_json@313:v.quiz.maths.q2.question>",                 "options": [                     "1",                     "2",                     "3",                     "<from_json@313:v.quiz.maths.q2.answer>"                 ],                 "answer": "4"             }         }     } }',
  '<_skip@76:c>   "XMDEwOlJlcG9zaXRvcnkxODQ2MjA4ODQ=": "<from_json@313:v.xmdewoljlcg9zaxrvcnkxodq2mja4odq=>" }',
  '<_skip@76:c>   "aliceblue": "<from_json@313:v.aliceblue>",   "antiquewhite": "<from_json@313:v.antiquewhite>",   "aqua": "<from_json@313:v.aqua>",   "aquamarine": "<from_json@313:v.aquamarine>",   "azure": "<from_json@313:v.azure>",   "beige": "<from_json@313:v.beige>",   "bisque": "<from_json@313:v.bisque>",   "black": "<from_json@313:v.black>",   "blanchedalmond": "<from_json@313:v.blanchedalmond>",   "blue": "<from_json@313:v.blue>",   "blueviolet": "<from_json@313:v.blueviolet>",   "brown": "<from_json@313:v.brown>",   "majenta": "<from_json@313:v.majenta>" }',
  '<_skip@76:c>   "colors":   [     <_from_json_raw@283:c>       "color": "black",       "category": "hue",       "type": "primary",       "code": {         "rgba": [255,255,255,1],         "hex": "#000"       }     },     {       "color": "white",       "category": "value",       "code": {         "rgba": [0,0,0,1],         "hex": "#FFF"       }     },     {       "color": "red",       "category": "hue",       "type": "primary",       "code": {         "rgba": [255,0,0,1],         "hex": "#FF0"       }     },     {       "color": "blue",       "category": "hue",       "type": "primary",       "code": {         "rgba": [0,0,255,1],         "hex": "#00F"       }     },     {       "color": "yellow",       "category": "hue",       "type": "primary",       "code": {         "rgba": [255,255,0,1],         "hex": "#FF0"       }     },     {       "color": "green",       "category": "hue",       "type": "secondary",       "code": {         "rgba": [0,255,0,1],         "hex": "#0F0"       }     }   ] }',
  '<_skip@76:c>"abcd":[],   "efgh":<_from_json_raw@283:c>"y":[],     "pqrstuv":  <from_json@313:v.efgh._124.wx>,     "p":  "",     "q":"" ,     "r": "" ,     "float1": <from_json@313:v.efgh.float4>,     "float2":1.0,     "float3":1.0 ,     "float4": 1.0 ,      "_124": {"wx" :  null,      "zzyym!!2@@39": [1.1, 2452, 398, {"x":[[4,53,6,[7  ,8,90 ],10]]}]} }  }',
  '<_skip@76:c>"emptya": [], "emptyh": <_from_json_raw@283:c>}, "emptystr":"", "<from_json@313:v.null>":null}',
  '<_skip@76:c>"menu":   <_from_json_raw@283:c>     "header": "<from_json@313:v.menu.header>",       "items": [       {"id": "Open"},       {"id": "OpenNew", "label": "Open New"},       null,       {"id": "ZoomIn", "label": "Zoom In"},       {"id": "ZoomOut", "label": "Zoom Out"},       {"id": "OriginalView", "label": "Original View"},       null,       {"id": "Quality"},       {"id": "Pause"},       {"id": "Mute"},       null,       {"id": "Find", "label": "Find..."},       {"id": "FindAgain", "label": "Find Again"},       {"id": "Copy"},       {"id": "CopyAgain", "label": "Copy Again"},       {"id": "CopySVG", "label": "Copy SVG"},       {"id": "ViewSVG", "label": "View SVG"},       {"id": "ViewSource", "label": "View Source"},       {"id": "SaveAs", "label": "Save As"},       null,       {"id": "Help"},       {"id": "About", "label": "About Adobe CVG Viewer..."}     ]   }}',
  '<_skip@76:c>"menu":   <_from_json_raw@283:c>     "id": "<from_json@313:v.menu.id>",       "value": "<from_json@313:v.menu.value>",       "popup": {         "menuitem": [         {"value": "New", "onclick": "CreateNewDoc()"},         {"value": "Open", "onclick": "OpenDoc()"},         {"value": "Close", "onclick": "CloseDoc()"}         ]       }   } }',
  '<_skip@76:c>"mykey1": [1, 2, 3], "mykey2": <from_json@313:v.mykey2>, "mykey":"\'`:<_from_json_raw@283:c>}<openA><closeA>&%[]\\\\^~|$\'"}',
  '<_skip@76:c>"widget":   <_from_json_raw@283:c>     "debug": "<from_json@313:v.widget.debug>",       "window": {         "title": "<from_json@313:v.widget.window.title>",         "name": "<from_json@313:v.widget.window.name>",         "width": <from_json@313:v.widget.window.height>,         "height": 500       },       "image": {         "src": "<from_json@313:v.widget.image.src>",         "name": "<from_json@313:v.widget.image.name>",         "hOffset": <from_json@313:v.widget.text.hoffset>,         "vOffset": 250,         "alignment": "<from_json@313:v.widget.text.alignment>"       },       "text": {         "data": "<from_json@313:v.widget.text.data>",         "size": <from_json@313:v.widget.text.size>,         "style": "<from_json@313:v.widget.text.style>",         "name": "<from_json@313:v.widget.text.name>",         "hOffset": 250,         "vOffset": <from_json@313:v.widget.text.voffset>,         "alignment": "center",         "onMouseUp": "<from_json@313:v.widget.text.onmouseup>"       }   } }'],
 '<_skip@76:c>': ['<<openA>lambda<closeA>@72:c>'],
 '<_from_json_raw@283:c>': ['[', '{'],
 '<openA>': ['<'],
 '<closeA>': ['<'],
 '<from_json@313:v.fruit>': ['Apple'],
 '<from_json@313:v.size>': ['Large'],
 '<from_json@313:v.color>': ['Red'],
 '<from_json@313:v.product>': ['Jam'],
 '<from_json@313:v.quiz.sport.q1.question>': ['Which one is correct team name in NBA?'],
 '<from_json@313:v.quiz.sport.q1.answer>': ['Huston Rocket'],
 '<from_json@313:v.quiz.maths.q1.question>': ['5 + 7 = ?'],
 '<from_json@313:v.quiz.maths.q1.answer>': ['12'],
 '<from_json@313:v.quiz.maths.q2.question>': ['12 - 8 = ?'],
 '<from_json@313:v.quiz.maths.q2.answer>': ['4'],
 '<from_json@313:v.xmdewoljlcg9zaxrvcnkxodq2mja4odq=>': ['-----BEGIN PGP SIGNATURE-----  iQIzBAABAQAdFiEESn/54jMNIrGSE6Tp6cQjvhfv7nAFAlnT71cACgkQ6cQjvhfv 7nCWwA//XVqBKWO0zF+                             bZl6pggvky3Oc2j1pNFuRWZ29LXpNuD5WUGXGG209B0hI DkmcGk19ZKUTnEUJV2Xd0R7AW01S/YSub7OYcgBkI7qUE13FVHN5ln1KvH2all2n 2+JCV1HcJLEoTjqIFZSSu/sMdhkLQ9/NsmMAzpf/           iIM0nQOyU4YRex9eD1bYj6nA OQPIDdAuaTQj1gFPHYLzM4zJnCqGdRlg0sOM/zC5apBNzIwlgREatOYQSCfCKV7k nrU34X8b9BzQaUx48Qa+Dmfn5KQ8dl27RNeWAqlkuWyv3pUauH9UeYW+KyuJeMkU +     NyHgAsWFaCFl23kCHThbLStMZOYEnGagrd0hnm1TPS4GJkV4wfYMwnI4KuSlHKB jHl3Js9vNzEUQipQJbgCgTiWvRJoK3ENwBTMVkKHaqT4x9U4Jk/                                                XZB6Q8MA09ezJ 3QgiTjTAGcum9E9QiJqMYdWQPWkaBIRRz5cET6HPB48YNXAAUsfmuYsGrnVLYbG+                                                                                      UpC6I97VybYHTy2O9XSGoaLeMI9CsFn38ycAxxbWagk5mhclNTP5mezIq6wKSwmr X11FW3n1J23fWZn5HJMBsRnUCgzqzX3871IqLYHqRJ/bpZ4h20RhTyPj5c/z7QXp eSakNQMfbbMcljkha+            ZMuVQX1K9aRlVqbmv3ZMWh+OijLYVU2bc= =5Io4 -----END PGP SIGNATURE----- '],
 '<from_json@313:v.aliceblue>': ['#f0f8ff'],
 '<from_json@313:v.antiquewhite>': ['#faebd7'],
 '<from_json@313:v.aqua>': ['#00ffff'],
 '<from_json@313:v.aquamarine>': ['#7fffd4'],
 '<from_json@313:v.azure>': ['#f0ffff'],
 '<from_json@313:v.beige>': ['#f5f5dc'],
 '<from_json@313:v.bisque>': ['#ffe4c4'],
 '<from_json@313:v.black>': ['#000000'],
 '<from_json@313:v.blanchedalmond>': ['#ffebcd'],
 '<from_json@313:v.blue>': ['#0000ff'],
 '<from_json@313:v.blueviolet>': ['#8a2be2'],
 '<from_json@313:v.brown>': ['#a52a2a'],
 '<from_json@313:v.majenta>': ['#ff0ff'],
 '<from_json@313:v.efgh._124.wx>': ['null'],
 '<from_json@313:v.efgh.float4>': ['1.0'],
 '<from_json@313:v.null>': ['null'],
 '<from_json@313:v.menu.header>': ['SVG Viewer'],
 '<from_json@313:v.menu.id>': ['file'],
 '<from_json@313:v.menu.value>': ['File'],
 '<from_json@313:v.mykey2>': ['null'],
 '<from_json@313:v.widget.debug>': ['on'],
 '<from_json@313:v.widget.window.title>': ['Sample Konfabulator Widget'],
 '<from_json@313:v.widget.window.name>': ['main_window'],
 '<from_json@313:v.widget.window.height>': ['500'],
 '<from_json@313:v.widget.image.src>': ['Images/Sun.png'],
 '<from_json@313:v.widget.image.name>': ['sun1'],
 '<from_json@313:v.widget.text.hoffset>': ['250'],
 '<from_json@313:v.widget.text.alignment>': ['center'],
 '<from_json@313:v.widget.text.data>': ['Click Here'],
 '<from_json@313:v.widget.text.size>': ['36'],
 '<from_json@313:v.widget.text.style>': ['bold'],
 '<from_json@313:v.widget.text.name>': ['text1'],
 '<from_json@313:v.widget.text.voffset>': ['100'],
 '<from_json@313:v.widget.text.onmouseup>': ['sun1.opacity = (sun1.opacity / 100) * 90;']}
In [310]:
(0, 1000)
In [311]:
(0, 100)

2.3  Results

Note that we found and fixed a bug in the Information flow chapter of the fuzzingbook, which was causing Autogram to fail (See flatten and ostr_new in recover_grammar_with_taints). This caused the precision numbers of Autogram to improve. However, please see the grammars generated. They are still enumerations.

In [312]:
In [313]:
In [314]:

2.3.1  Table II (Time in Seconds)

In [315]:
Out[315]:
{'calculator.py': (552209, datetime.timedelta(seconds=6, microseconds=552209)),
 'mathexpr.py': (538847, datetime.timedelta(seconds=26, microseconds=538847)),
 'urlparse.py': (997539, datetime.timedelta(seconds=47, microseconds=997539)),
 'netrc.py': (167983, datetime.timedelta(seconds=179, microseconds=167983)),
 'cgidecode.py': (905319, datetime.timedelta(seconds=24, microseconds=905319)),
 'microjson.py': (656220,
  datetime.timedelta(seconds=450, microseconds=656220))}
In [316]:
Out[316]:
{'calculator.py': (718471, datetime.timedelta(seconds=6, microseconds=718471)),
 'mathexpr.py': (21477, datetime.timedelta(seconds=17, microseconds=21477)),
 'urlparse.py': (125374, datetime.timedelta(seconds=6, microseconds=125374)),
 'netrc.py': (384119, datetime.timedelta(seconds=30, microseconds=384119)),
 'cgidecode.py': (833595, datetime.timedelta(seconds=31, microseconds=833595)),
 'microjson.py': (952269,
  datetime.timedelta(seconds=407, microseconds=952269))}
In [317]:
TimingAutogramMimid
calculator.py66
mathexpr.py2617
urlparse.py476
netrc.py17930
cgidecode.py2431
microjson.py450407

2.3.2  Table III (Precision)

How many inputs we generate using our inferred grammar is valid? (accepted by the subject program?)

Note that the paper reports precision per 100 inputs. We have increased the count to 1000.

In [318]:
Out[318]:
{'calculator.py': (395, 1000),
 'mathexpr.py': (301, 1000),
 'urlparse.py': (1000, 1000),
 'netrc.py': (30, 1000),
 'cgidecode.py': (460, 1000),
 'microjson.py': (0, 1000)}
In [319]:
Out[319]:
{'calculator.py': (1000, 1000),
 'mathexpr.py': (699, 1000),
 'urlparse.py': (1000, 1000),
 'netrc.py': (773, 1000),
 'cgidecode.py': (1000, 1000),
 'microjson.py': (924, 1000)}
In [320]:
PrecisionAutogramMimid
calculator.py3951000
mathexpr.py301699
urlparse.py10001000
netrc.py30773
cgidecode.py4601000
microjson.py0924

2.3.3  Table IV (Recall)

How many valid inputs generated by the golden grammar or collected externally are parsable by a parser using our grammar?

Note that the recall is reported per 100 inputs in paper. We have increased the count to 1000. For Microjson, the recall numbers are based on 100 realworld documents. These are available in json.tar.gz that is bundled along with this notebook.

In [321]:
Out[321]:
{'calculator.py': (1, 1000),
 'mathexpr.py': (0, 1000),
 'urlparse.py': (277, 1000),
 'netrc.py': (773, 1000),
 'cgidecode.py': (380, 1000),
 'microjson.py': (0, 100)}
In [322]:
Out[322]:
{'calculator.py': (1000, 1000),
 'mathexpr.py': (922, 1000),
 'urlparse.py': (153, 1000),
 'netrc.py': (949, 1000),
 'cgidecode.py': (1000, 1000),
 'microjson.py': (93, 100)}
In [323]:
RecallAutogramMimid
calculator.py11000
mathexpr.py0922
urlparse.py277153
netrc.py773949
cgidecode.py3801000
microjson.py093

2.4  Using a Recognizer (not a Parser)

In [324]:
In [325]:
In [326]:
Out[326]:
{'<START>': ['<parse_expr-0-c>'],
 '<parse_expr-0-c>': ['<parse_expr-1>', '<parse_expr-2-s><parse_expr-1>'],
 '<parse_expr-1>': ['(<parse_expr-0-c>)', '<parse_num-1-s>'],
 '<parse_expr-2-s>': ['<parse_expr-1><parse_expr>',
  '<parse_expr-1><parse_expr><parse_expr-2-s>'],
 '<parse_num-1-s>': ['<is_digit-0-c>', '<is_digit-0-c><parse_num-1-s>'],
 '<is_digit-0-c>': ['0', '1', '2', '3', '4', '5', '6', '7', '8', '9'],
 '<parse_expr>': ['*', '+', '-', '/']}

2.5  Parsing with Parser Combinators

2.5.1  Helper

In [352]:
In [353]:

2.5.2  Subject - assignment

In [354]:

2.5.3  Sample

In [355]:

2.5.4  Recovering the parse tree

In [356]:
In [357]:
In [358]:
Out[358]:

2.6  Parsing with PEG Parser

In [334]:

2.6.1  PEG samples

In [335]:
In [336]:
In [337]:
Out[337]: